İki Sıralı Dizinin Ortancası
İki sıralı dizinin ortancası problemini, kısa dizinin bölme sınırında ikili arama kullanarak O(log(min(m,n))) sürede çözün.
İki Sıralı Dizinin Ortancası, CoddyKit'te ücretsiz bir DSA Interview Prep dersidir. Bu, 4 dersinin 4. dersidir. Aşağıdan dersin tamamını ücretsiz okuyabilir, sonra tarayıcıda yerleşik kod editörü ve 7/24 yapay zeka koçu ile uygulamalı olarak pratik yapabilirsin. Bu, DSA Interview Prep öğrenme yolunun bir parçasıdır ve ilerlemeniz web ve CoddyKit uygulaması arasında senkronize olur. DSA Interview Prep kursu toplamda 4 dersten oluşur.
İki Sıralı Dizinin Medyanı
İki Sıralı Dizinin Medyanı (LeetCode 4), klasik bir zor problemdir. Uzunlukları m ve n olan iki sıralı dizi nums1 ve nums2 verildiğinde, bunların birleştirilmiş sıralı dizisinin medyanını O(log(min(m,n))) zamanda bulunuz. Naif yaklaşım, her iki diziyi O(m+n) zamanda birleştirir; ancak en iyi çözüm bölüm sınırları üzerinde ikili arama kullanır. Bu, önde gelen teknoloji şirketlerinde en sık sorulan zor problemlerden biridir.
# 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))Naif Birleştirme Yaklaşımı
En basit O(m+n) yaklaşım: her iki sıralı diziyi birleştiriniz, ardından medyanı bulunuz. İki sıralı diziyi birleştirmek O(m+n)'dir. Uzunluğu L olan bir dizinin medyanı, L tek ise arr[L//2], çift ise (arr[L//2-1] + arr[L//2]) / 2 olur. Bu doğrudur ancak O(log(min(m,n))) gereksinimini karşılamaz. Bir mülakatta temel bir referans noktası oluşturmak için bunu her zaman önce sununuz, ardından iyileştiriniz.
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.5Bölümleme Fikri
Temel içgörü: medyan, birleşik diziyi iki eşit yarıya böler. Şu koşulları sağlayan bir nums1 bölümü ve nums2 bölümü bulmamız gerekir: (1) Sol yarıların toplam boyutu sağ yarılarınkiyle aynı olmalıdır. (2) Sol yarılardaki tüm öğeler, sağ yarılardaki tüm öğelerden ≤ olmalıdır. nums1 içindeki doğru bölüm noktasını bulmak için ikili arama yaparsak, nums2 içindeki bölüm noktası toplam uzunluk koşuluyla otomatik olarak belirlenir.
# 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])Bölümleme Üzerinde İkili Arama
Daha kısa dizi olan nums1'in i bölümleme indeksi üzerinde ikili arama yapınız. nums2'deki j bölümleme indeksi, j = (m+n+1)//2 - i olarak belirlenir (sol yarıların (m+n+1)//2 öğe içermesini sağlar). Bölümleme, nums1[i-1] ≤ nums2[j] ve nums2[j-1] ≤ nums1[i] olduğunda geçerlidir. İkili arama, bu dengeyi bulmak için i'yi artırır veya azaltır.
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.5İkili Aramayı İzleme
nums1=[1,3], nums2=[2] için izleme: 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). Kontrol: 1≤inf ve 2≤3 ✓. Toplam tek: max(1,2)=2.0 değerini döndürünüz. ✓ Algoritma ilk adımda bölümü buldu; çünkü dizi boyutları küçüktür.
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]))Neden Daha Kısa Dizi Üzerinde İkili Arama Yapılır
O(log(m+n)) yerine O(log(min(m,n))) elde etmek için daha kısa dizi üzerinde ikili arama yaparız. Daha uzun dizinin bölümlemesi, kısa dizideki bölümleme tarafından tamamen belirlenir. len(nums1) > len(nums2) ise girdileri yer değiştirmek, kısa dizinin her zaman arama alanı olmasını sağlar. Değişmez: j, i ve toplam uzunluktan türetildiğinde nums2 için her zaman geçerli bir bölümleme indeksidir.
# 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}')Çift ve Tek Toplam Uzunlukları Ele Alma
Birleşik uzunluk tek olduğunda: medyan, sol yarıların maksimumudur (max(max_left1, max_left2)). Çift olduğunda: medyan, sol yarıların maksimumu ile sağ yarıların minimumunun ortalamasıdır. Sol yarı boyutu için (m+n+1)//2 formülü her iki durumda da çalışır: çift toplam için n//2 değerini verir (solda bir fazla öğe olacak şekilde) ve çift medyanı elde etmek için min_right ile ortalamasını alırız.
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 arraySınır Durumları
Kritik sınır durumları: (1) Bir dizi boş — boş olmayan dizinin medyanı. (2) Bir dizinin tüm öğeleri diğerinden küçük — bölümleme bir uç noktaya gider. (3) Yinelenen öğeler — algoritma bunları doğal biçimde ele alır. (4) Her iki dizinin uzunluğu 1 — iki öğeli basit medyan. Kodlamadan sonra bu durumları her zaman sınayınız. Nöbetçi değerler -∞ ve +∞, sınır bölümlemelerini (i=0 veya i=m) düzgün biçimde ele alır.
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.5Genelleme: İki Dizideki k'ncı En Küçük Öğe
Medyan problemi, iki sıralı dizi genelinde k'ncı en küçük öğeyi bulacak şekilde genelleştirilebilir. Her adımda her dizinin k//2'nci öğesini karşılaştırınız. Daha küçük yarıyı eleyiniz: bu k//2 öğenin tamamı k'ncı öğeden küçüktür; onları atabiliriz. k'yi k//2 azaltıp özyineleyiniz. Temel durumlar: bir dizi boşsa (kalan dizinin k'ncı öğesini döndürünüz) veya k=1 ise (iki dizinin başındaki öğelerin minimumunu döndürünüz). Zaman: 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)}')Tüm Yaklaşımların Karşılaştırılması
Son karşılaştırma: Dizileri birleştirme: O(m+n) time, O(m+n) alan. Bölümleme üzerinde ikili arama: O(log(min(m,n))) time, O(1) alan. k'inci en küçük için özyineleme: O(log(m+n)) time, O(log k) çağrı yığını. İkili arama ile bölümleme yöntemi, mülakat yapanların bu problem için beklediği yöntemdir. Bu, açıkça açıklanması en zor yaygın LeetCode problemidir — bölümleme mantığını ve dört sınır kontrolünü otomatikleşene kadar çalışın.
# 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')Mülakat İletişim Stratejisi
Bir mülakatta bu zor problem için: (1) Naif O(m+n) birleştirme yaklaşımını hemen belirtin — bu, yetkinliğinizi gösterir. (2) O(log(min(m,n))) hedefini ve bölümleme fikrini açıklayın. (3) Bölümleme değişmezini adım adım ele alın: max_left1 ≤ min_right2 ve max_left2 ≤ min_right1. (4) Nöbetçi değerleri açıkça ele alın. (5) Tek ve çift uzunluk için ortanca formülünü belirtin. (6) 1-2 örnekle test edin. Bu 5 adımlı çerçeve, baskı altında çok az adayın kusursuz çözebildiği bir problemde bile sistematik problem çözme becerinizi gösterir.
# 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.5Hızlı Kontrol
Bu dersteki Veri Yapıları & Algoritmalar — Kodlama Mülakatına Hazırlık kavramlarını anlayışınızı sınayın.
Ders Özeti
Bu derste şunları öğrendiniz: iki sıralı dizinin ortancası, kısa olan dizide doğru bölümleme sınırını bulmak için O(log(min(m,n))) karmaşıklığında ikili arama yapılarak bulunabilir, bölümleme, max_left1 ≤ min_right2 ve max_left2 ≤ min_right1 olduğunda geçerlidir; nöbetçi değerler sınır durumlarını ele alır ve k'inci en küçük genellemesi, O(log k) time karmaşıklığında özyinelemeli yarı eleme yaklaşımını kullanır. Böl ve Yönet derslerini tamamladığınız için tebrikler — artık kodlama mülakatları için kapsamlı bir araç setiniz var!
Sıkça Sorulan Sorular
“İki Sıralı Dizinin Ortancası” dersi ücretsiz mi?
Evet — “İki Sıralı Dizinin Ortancası” dersin tüm metni burada web'de ücretsiz olarak okunabilir. Etkileşimli olarak pratik yapmak (yerleşik kod editörü ve 7/24 yapay zeka koçu) ve DSA Interview Prep kursunun geri kalanını açmak için CoddyKit PRO'ya yükselt. DSA Interview Prep kursu toplamda 4 dersten oluşur.
“İki Sıralı Dizinin Ortancası” dersinde ne öğreneceğim?
İki sıralı dizinin ortancası problemini, kısa dizinin bölme sınırında ikili arama kullanarak O(log(min(m,n))) sürede çözün. DSA Interview Prep ile uygulamalı kodu tarayıcıda doğrudan çalıştırarak pratik yaparsın ve 7/24 yapay zeka koçu dersi çalışırken sorularını yanıtlar.
DSA Interview Prep öğrenmeye başlamak için deneyim gerekli mi?
Önceden deneyim gerekmez. CoddyKit'te DSA Interview Prep, başlangıçtan ileri seviyeye kadar yapılandırıldığı için buradan başlayabilir veya başından başlayıp kendi hızında ilerleme yapabilirsin. Bu, 4 dersinin 4. dersidir.
“İki Sıralı Dizinin Ortancası” dersi ne kadar sürer?
Çoğu CoddyKit dersi yaklaşık 5–10 dakika sürer. Her biri kısa ve etkileşimli olduğu için sabit ilerleme yaparsın ve web ile uygulama arasında tam olarak bıraktığın yerden devam edebilirsin.
Bu DSA Interview Prep dersinde kod yazıp çalıştırabilir miyim?
Evet. Her DSA Interview Prep dersi yerleşik bir kod editörü içerir, bu sayede tarayıcıda gerçek kod yazıp çalıştırabilir ve anlık yapay zeka geri bildirimi alırsın — yerel kurulum gerekli değildir.
Bu kursun tüm dersleri
- Böl ve Yönet Şablonu
- Değiştirilmiş Birleştirmeli Sıralamayla Terslikleri Sayma
- Çoğunluk Öğesi: Boyer-Moore Oylaması
- İki Sıralı Dizinin Ortancası