Median dari Dua Array Terurut
Selesaikan masalah median dari dua array terurut dalam O(log(min(m,n))) menggunakan pencarian biner pada batas partisi array yang lebih pendek
Median dari Dua Array Terurut adalah pelajaran DSA Interview Prep gratis di CoddyKit. Ini adalah pelajaran 4 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar DSA Interview Prep, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus DSA Interview Prep mencakup 4 pelajaran total.
Median Dua Larik Terurut
Median Dua Larik Terurut (LeetCode 4) merupakan soal sulit klasik. Diberikan dua larik terurut nums1 (berukuran m) dan nums2 (berukuran n), temukan median dari urutan terurut gabungannya dalam waktu O(log(min(m,n))). Pendekatan naif menggabungkan kedua larik dalam O(m+n), tetapi solusi optimal menggunakan pencarian biner pada batas partisi. Ini merupakan salah satu soal sulit yang paling sering ditanyakan di perusahaan teknologi terkemuka.
# Examples:
nums1 = [1, 3]
nums2 = [2]
# Combined sorted: [1, 2, 3] → median = 2.0
nums1b = [1, 2]
nums2b = [3, 4]
# Combined sorted: [1, 2, 3, 4] → median = (2+3)/2 = 2.5
print('Example 1 median:', 2.0)
print('Example 2 median:', 2.5)
print('Total length:', len(nums1)+len(nums2), 'and', len(nums1b)+len(nums2b))Pendekatan Penggabungan Naif
Pendekatan O(m+n) yang paling sederhana: gabungkan kedua larik terurut, lalu temukan mediannya. Menggabungkan dua larik terurut membutuhkan O(m+n). Median larik berukuran L adalah arr[L//2] jika L ganjil, atau (arr[L//2-1] + arr[L//2]) / 2 jika L genap. Pendekatan ini benar, tetapi tidak memenuhi persyaratan O(log(min(m,n))). Dalam wawancara, selalu sajikan pendekatan ini terlebih dahulu untuk menetapkan dasar, lalu optimalkan.
def find_median_naive(nums1, nums2):
# Merge two sorted arrays
merged = []
i = j = 0
while i < len(nums1) and j < len(nums2):
if nums1[i] <= nums2[j]:
merged.append(nums1[i]); i += 1
else:
merged.append(nums2[j]); j += 1
merged += nums1[i:] + nums2[j:]
L = len(merged)
if L % 2 == 1:
return float(merged[L // 2])
return (merged[L//2 - 1] + merged[L//2]) / 2.0
print(find_median_naive([1,3],[2])) # 2.0
print(find_median_naive([1,2],[3,4])) # 2.5Gagasan Partisi
Inti pentingnya: median membagi larik gabungan menjadi dua bagian yang sama besar. Kita perlu menemukan partisi pada nums1 dan partisi pada nums2 sehingga: (1) Total ukuran bagian kiri sama dengan total ukuran bagian kanan. (2) Semua elemen di bagian kiri ≤ semua elemen di bagian kanan. Jika kita melakukan pencarian biner untuk menemukan titik partisi yang tepat di nums1, partisi di nums2 ditentukan secara otomatis berdasarkan batasan panjang total.
# Partition concept visualised:
# nums1: [1, 3] | [5, 7] (partition after index 1)
# nums2: [2, 4] | [6, 8] (partition after index 1)
# Combined left: [1, 3, 2, 4] = 4 elements
# Combined right: [5, 7, 6, 8] = 4 elements
# Valid if max(left) <= min(right): max(3,4)=4 <= min(5,6)=5 ✓
# Median = (max_left + min_right) / 2 = (4+5)/2 = 4.5
nums1, nums2 = [1,3,5,7], [2,4,6,8]
merged = sorted(nums1+nums2)
print('Merged:', merged)
L = len(merged)
print('Median:', (merged[L//2-1]+merged[L//2])/2 if L%2==0 else merged[L//2])Pencarian Biner pada Partisi
Lakukan pencarian biner pada indeks i partisi nums1 (larik yang lebih pendek). Indeks j partisi pada nums2 ditentukan sebagai j = (m+n+1)//2 - i (untuk memastikan bagian kiri memiliki (m+n+1)//2 elemen). Partisi valid jika nums1[i-1] ≤ nums2[j] dan nums2[j-1] ≤ nums1[i]. Pencarian biner menyesuaikan i ke atas atau ke bawah untuk menemukan keseimbangan ini.
def find_median_sorted_arrays(nums1, nums2):
# Ensure nums1 is the shorter array
if len(nums1) > len(nums2):
return find_median_sorted_arrays(nums2, nums1)
m, n = len(nums1), len(nums2)
lo, hi = 0, m
while lo <= hi:
i = (lo + hi) // 2 # partition index in nums1
j = (m + n + 1) // 2 - i # partition index in nums2
# Boundary values with sentinels
max_left1 = float('-inf') if i == 0 else nums1[i-1]
min_right1 = float('inf') if i == m else nums1[i]
max_left2 = float('-inf') if j == 0 else nums2[j-1]
min_right2 = float('inf') if j == n else nums2[j]
if max_left1 <= min_right2 and max_left2 <= min_right1:
# Found the correct partition
if (m + n) % 2 == 1:
return float(max(max_left1, max_left2))
return (max(max_left1, max_left2) + min(min_right1, min_right2)) / 2.0
elif max_left1 > min_right2:
hi = i - 1 # i is too large, move left
else:
lo = i + 1 # i is too small, move right
return 0.0
print(find_median_sorted_arrays([1,3],[2])) # 2.0
print(find_median_sorted_arrays([1,2],[3,4])) # 2.5Menelusuri Pencarian Biner
Telusuri nums1=[1,3], nums2=[2]: m=2, n=1, total=3, lo=0, hi=2. i=(0+2)//2=1, j=(2+1+1)//2-1=1. max_left1=nums1[0]=1, min_right1=nums1[1]=3, max_left2=nums2[0]=2, min_right2=inf (j=1=n). Periksa: 1≤inf dan 2≤3 ✓. Total ganjil: kembalikan max(1,2)=2.0. ✓ Algoritma menemukan partisi pada langkah pertama karena ukuran lariknya kecil.
def find_median_traced(nums1, nums2):
if len(nums1) > len(nums2):
return find_median_traced(nums2, nums1)
m, n = len(nums1), len(nums2)
lo, hi = 0, m
step = 0
while lo <= hi:
step += 1
i = (lo + hi) // 2
j = (m + n + 1) // 2 - i
ml1 = float('-inf') if i==0 else nums1[i-1]
mr1 = float('inf') if i==m else nums1[i]
ml2 = float('-inf') if j==0 else nums2[j-1]
mr2 = float('inf') if j==n else nums2[j]
print(f'Step {step}: i={i},j={j}, ml1={ml1},mr1={mr1},ml2={ml2},mr2={mr2}')
if ml1<=mr2 and ml2<=mr1:
if (m+n)%2==1: return float(max(ml1,ml2))
return (max(ml1,ml2)+min(mr1,mr2))/2.0
elif ml1>mr2: hi=i-1
else: lo=i+1
return 0.0
print(find_median_traced([1,3],[2]))Mengapa Pencarian Biner Dilakukan pada Larik yang Lebih Pendek
Kita melakukan pencarian biner pada larik yang lebih pendek untuk mencapai O(log(min(m,n)), bukan O(log(m+n)). Partisi larik yang lebih panjang sepenuhnya ditentukan oleh partisi larik yang lebih pendek. Menukar masukan jika len(nums1) > len(nums2) memastikan larik yang lebih pendek selalu menjadi ruang pencarian. Invariannya: ketika j diturunkan dari i dan panjang total, j selalu merupakan indeks partisi yang valid untuk nums2.
# Prove j is always valid:
# Total elements in left halves = (m+n+1)//2
# Left from nums1: i elements (0 <= i <= m)
# Left from nums2: j = (m+n+1)//2 - i elements
# j must be in [0, n]:
# j >= 0: i <= (m+n+1)//2 <= (m+n+1)//2 ≤ ... always true for valid lo/hi
# j <= n: i >= (m+n+1)//2 - n = (m-n+1)//2 >= 0 (since m <= n)
m, n = 3, 5 # m <= n
half = (m+n+1)//2
for i in range(m+1):
j = half - i
valid = 0 <= j <= n
print(f'i={i}: j={j}, valid={valid}')Menangani Panjang Total Ganjil dan Genap
Ketika panjang gabungan ganjil: median adalah nilai maksimum dari bagian kiri (max(max_left1, max_left2)). Ketika genap: median adalah rata-rata nilai maksimum dari bagian kiri dan nilai minimum dari bagian kanan. Rumus (m+n+1)//2 untuk ukuran bagian kiri berlaku untuk keduanya: untuk total genap, rumus ini menghasilkan n//2 (satu elemen tambahan di bagian kiri), lalu kita menghitung rata-ratanya dengan min_right untuk mendapatkan median genap.
def median_demo(a, b):
merged = sorted(a + b)
L = len(merged)
expected = merged[L//2] if L%2==1 else (merged[L//2-1]+merged[L//2])/2
computed = find_median_sorted_arrays(a[:], b[:])
print(f'a={a}, b={b}: merged={merged}, median={expected}, computed={computed}')
assert abs(expected - computed) < 1e-9
def find_median_sorted_arrays(nums1, nums2):
if len(nums1)>len(nums2): return find_median_sorted_arrays(nums2,nums1)
m,n=len(nums1),len(nums2); lo,hi=0,m
while lo<=hi:
i=(lo+hi)//2; j=(m+n+1)//2-i
ml1=float('-inf') if i==0 else nums1[i-1]; mr1=float('inf') if i==m else nums1[i]
ml2=float('-inf') if j==0 else nums2[j-1]; mr2=float('inf') if j==n else nums2[j]
if ml1<=mr2 and ml2<=mr1:
if (m+n)%2==1: return float(max(ml1,ml2))
return (max(ml1,ml2)+min(mr1,mr2))/2.0
elif ml1>mr2: hi=i-1
else: lo=i+1
return 0.0
median_demo([1,3],[2])
median_demo([1,2],[3,4])
median_demo([],[1])
median_demo([2],[]) # single arrayKasus Tepi
Kasus tepi penting: (1) Salah satu larik kosong—median larik yang tidak kosong. (2) Semua elemen salah satu larik lebih kecil daripada elemen di larik lainnya—partisi berada di salah satu ujung. (3) Elemen duplikat—algoritma menanganinya secara alami. (4) Kedua larik berukuran 1—median dua elemen yang sederhana. Selalu uji kasus-kasus ini setelah menulis kode. Nilai sentinel -∞ dan +∞ menangani partisi batas (i=0 atau i=m) dengan baik.
def fmsa(a,b):
if len(a)>len(b): return fmsa(b,a)
m,n=len(a),len(b); lo,hi=0,m
while lo<=hi:
i=(lo+hi)//2; j=(m+n+1)//2-i
ml1=float('-inf') if i==0 else a[i-1]; mr1=float('inf') if i==m else a[i]
ml2=float('-inf') if j==0 else b[j-1]; mr2=float('inf') if j==n else b[j]
if ml1<=mr2 and ml2<=mr1:
if (m+n)%2==1: return float(max(ml1,ml2))
return (max(ml1,ml2)+min(mr1,mr2))/2.0
elif ml1>mr2: hi=i-1
else: lo=i+1
# Edge cases
print(fmsa([], [1])) # 1.0
print(fmsa([2], [])) # 2.0
print(fmsa([1,2], [3,4])) # 2.5
print(fmsa([3,4], [1,2])) # 2.5
print(fmsa([1,1,1], [1,1])) # 1.0 (duplicates)
print(fmsa([10,20,30],[5,15,25,35])) # 17.5Generalisasi: Elemen Terkecil ke-K
Masalah median dapat digeneralisasi menjadi pencarian elemen terkecil ke-k di antara dua larik terurut. Pada setiap langkah, bandingkan elemen ke-k//2 dari setiap larik. Singkirkan separuh yang lebih kecil: k//2 elemen tersebut semuanya lebih kecil daripada elemen ke-k, sehingga kita dapat membuangnya. Kurangi k sebesar k//2 lalu lakukan rekursi. Kasus dasar: salah satu larik kosong (kembalikan elemen ke-k dari larik yang tersisa), atau k=1 (kembalikan nilai minimum dari bagian depan kedua larik). Waktu: O(log k) = O(log(m+n)).
def kth_smallest(nums1, nums2, k):
if not nums1: return nums2[k-1]
if not nums2: return nums1[k-1]
if k == 1: return min(nums1[0], nums2[0])
# Compare k//2-th elements
half = k // 2
i = min(half, len(nums1)) - 1 # index in nums1
j = min(half, len(nums2)) - 1 # index in nums2
if nums1[i] <= nums2[j]:
# Eliminate first (i+1) elements of nums1
return kth_smallest(nums1[i+1:], nums2, k - (i+1))
else:
return kth_smallest(nums1, nums2[j+1:], k - (j+1))
nums1, nums2 = [1,3,5,7], [2,4,6,8]
for k in range(1, 9):
print(f'k={k}: {kth_smallest(nums1[:], nums2[:], k)}')Membandingkan Semua Pendekatan
Perbandingan akhir: Penggabungan larik: O(m+n) time, ruang O(m+n). Pencarian biner pada partisi: O(log(min(m,n))) time, ruang O(1). Rekursi elemen terkecil ke-k: O(log(m+n)) time, tumpukan pemanggilan O(log k). Metode partisi dengan pencarian biner adalah metode yang diharapkan pewawancara untuk masalah ini. Ini adalah masalah umum LeetCode yang paling sulit dijelaskan dengan jelas—berlatihlah logika partisi dan keempat pemeriksaan batas sampai menjadi otomatis.
# Performance comparison
import time, random
def merge_median(a, b):
merged = sorted(a+b)
L=len(merged)
return merged[L//2] if L%2==1 else (merged[L//2-1]+merged[L//2])/2
def binary_median(a, b):
if len(a)>len(b): return binary_median(b,a)
m,n=len(a),len(b);lo,hi=0,m
while lo<=hi:
i=(lo+hi)//2;j=(m+n+1)//2-i
ml1=float('-inf') if i==0 else a[i-1];mr1=float('inf') if i==m else a[i]
ml2=float('-inf') if j==0 else b[j-1];mr2=float('inf') if j==n else b[j]
if ml1<=mr2 and ml2<=mr1:
if (m+n)%2==1: return float(max(ml1,ml2))
return (max(ml1,ml2)+min(mr1,mr2))/2.0
elif ml1>mr2: hi=i-1
else: lo=i+1
for size in [100, 10000]:
a = sorted(random.sample(range(size*2), size))
b = sorted(random.sample(range(size*2), size))
t1=time.time(); [merge_median(a,b) for _ in range(1000)]; t1=time.time()-t1
t2=time.time(); [binary_median(a,b) for _ in range(1000)]; t2=time.time()-t2
print(f'n={size}: merge={t1:.4f}s, binary={t2:.4f}s, speedup={t1/t2:.1f}x')Strategi Komunikasi Wawancara
Untuk masalah sulit ini dalam wawancara: (1) Nyatakan pendekatan penggabungan naif O(m+n) segera—ini menunjukkan kompetensi. (2) Jelaskan target O(log(min(m,n))) dan gagasan partisi. (3) Telusuri invarian partisi: max_left1 ≤ min_right2 dan max_left2 ≤ min_right1. (4) Tangani nilai sentinel secara eksplisit. (5) Nyatakan rumus median untuk jumlah elemen ganjil/genap. (6) Ujilah dengan 1–2 contoh. Kerangka kerja 5 langkah ini menunjukkan pemecahan masalah yang sistematis, bahkan pada masalah yang hanya dapat diselesaikan dengan sempurna oleh sedikit kandidat saat berada di bawah tekanan.
# Clean final solution for interviews:
def findMedianSortedArrays(nums1, nums2):
if len(nums1) > len(nums2):
return findMedianSortedArrays(nums2, nums1)
m, n = len(nums1), len(nums2)
lo, hi = 0, m
while lo <= hi:
i = (lo + hi) // 2
j = (m + n + 1) // 2 - i
max_l1 = nums1[i-1] if i > 0 else float('-inf')
min_r1 = nums1[i] if i < m else float('inf')
max_l2 = nums2[j-1] if j > 0 else float('-inf')
min_r2 = nums2[j] if j < n else float('inf')
if max_l1 <= min_r2 and max_l2 <= min_r1:
if (m + n) % 2:
return float(max(max_l1, max_l2))
return (max(max_l1, max_l2) + min(min_r1, min_r2)) / 2.0
elif max_l1 > min_r2: hi = i - 1
else: lo = i + 1
# Time: O(log(min(m,n))), Space: O(1)
print(findMedianSortedArrays([1,3],[2])) # 2.0
print(findMedianSortedArrays([1,2],[3,4])) # 2.5Uji Cepat
Ujilah pemahaman Anda tentang konsep Struktur Data & Algoritma — Persiapan Wawancara Pemrograman dari pelajaran ini.
Ringkasan Pelajaran
Dalam pelajaran ini Anda telah mempelajari: median dari dua larik terurut dapat ditemukan dalam O(log(min(m,n))) dengan melakukan pencarian biner untuk menemukan batas partisi yang benar pada larik yang lebih pendek, partisi valid ketika max_left1 ≤ min_right2 dan max_left2 ≤ min_right1, dengan nilai sentinel yang menangani kasus batas, serta generalisasi elemen terkecil ke-k menggunakan pendekatan eliminasi separuh secara rekursif dalam O(log k) time. Selamat telah menyelesaikan pelajaran Memecah dan Menaklukkan—sekarang Anda memiliki perangkat yang komprehensif untuk wawancara pemrograman!
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Median dari Dua Array Terurut” gratis?
Ya — teks lengkap “Median dari Dua Array Terurut” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus DSA Interview Prep, upgrade ke CoddyKit PRO. Kursus DSA Interview Prep mencakup 4 pelajaran total.
Apa yang akan aku pelajari di “Median dari Dua Array Terurut”?
Selesaikan masalah median dari dua array terurut dalam O(log(min(m,n))) menggunakan pencarian biner pada batas partisi array yang lebih pendek Kamu berlatih DSA Interview Prep dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.
Apakah aku perlu pengalaman untuk memulai DSA Interview Prep?
Tidak diperlukan pengalaman sebelumnya. DSA Interview Prep di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 4 dari 4.
Berapa lama pelajaran “Median dari Dua Array Terurut” memakan waktu?
Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.
Bisakah aku menulis dan menjalankan kode dalam pelajaran DSA Interview Prep ini?
Ya. Setiap pelajaran DSA Interview Prep menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.
Semua pelajaran dalam kursus ini
- Templat Divide and Conquer
- Menghitung Inversi Menggunakan Merge Sort Termodifikasi
- Elemen Mayoritas: Pemungutan Suara Boyer-Moore
- Median dari Dua Array Terurut