Median zweier sortierter Arrays
Lösen Sie median-of-two-sorted-arrays in O(log(min(m,n))) mithilfe einer binären Suche nach der Partitionsgrenze des kürzeren Arrays.
Median zweier sortierter Arrays ist eine kostenlose Coding Interview Prep-Lektion auf CoddyKit. Dies ist Lektion 4 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des Coding Interview Prep-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der Coding Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Der Median zweier sortierter Arrays
Median of Two Sorted Arrays (LeetCode 4) ist ein klassisches schwieriges Problem. Bei zwei sortierten Arrays nums1 (Länge m) und nums2 (Länge n) soll der Median ihrer zusammengeführten sortierten Folge in O(log(min(m,n))) Zeit gefunden werden. Ein naiver Ansatz führt beide Arrays in O(m+n) zusammen, doch die optimale Lösung verwendet eine binäre Suche über Partitionsgrenzen. Dies ist eines der am häufigsten gestellten schwierigen Probleme bei führenden Technologieunternehmen.
# 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))Naiver Merge-Ansatz
Der einfachste Ansatz mit O(m+n): Führen Sie beide sortierten Arrays zusammen und bestimmen Sie anschließend den Median. Das Zusammenführen zweier sortierter Arrays benötigt O(m+n). Der Median eines Arrays der Länge L ist arr[L//2], wenn L ungerade ist, oder (arr[L//2-1] + arr[L//2]) / 2, wenn L gerade ist. Dieser Ansatz ist korrekt, erfüllt aber nicht die Anforderung O(log(min(m,n))). Stellen Sie ihn in einem Vorstellungsgespräch immer zuerst vor, um eine Ausgangsbasis zu schaffen, und optimieren Sie anschließend.
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.5Die Partitionierungsidee
Die zentrale Erkenntnis: Der Median teilt das kombinierte Array in zwei gleich große Hälften. Wir müssen eine Partition von nums1 und eine Partition von nums2 finden, sodass: (1) Die linken Hälften insgesamt genauso viele Elemente enthalten wie die rechten Hälften. (2) Alle Elemente in den linken Hälften ≤ allen Elementen in den rechten Hälften sind. Wenn wir per binärer Suche den richtigen Partitionspunkt in nums1 suchen, wird die Partition in nums2 durch die Bedingung für die Gesamtlänge automatisch bestimmt.
# 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])Binäre Suche nach der Partition
Führen Sie eine binäre Suche über dem Partitionsindex i von nums1 (dem kürzeren Array) durch. Der Partitionsindex j in nums2 wird als j = (m+n+1)//2 - i bestimmt (damit die linken Hälften (m+n+1)//2 Elemente enthalten). Die Partition ist gültig, wenn nums1[i-1] ≤ nums2[j] und nums2[j-1] ≤ nums1[i] gilt. Die binäre Suche passt i nach oben oder unten an, um dieses Gleichgewicht zu finden.
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.5Nachverfolgen der binären Suche
Verfolgen wir 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). Prüfung: 1≤inf und 2≤3 ✓. Gesamtlänge ungerade: Geben Sie max(1,2)=2.0 zurück. ✓ Der Algorithmus hat die Partition bereits im ersten Schritt gefunden, weil die Arraygrößen klein sind.
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]))Warum die binäre Suche im kürzeren Array erfolgt
Wir führen die binäre Suche über dem kürzeren Array durch, um O(log(min(m,n))) statt O(log(m+n)) zu erreichen. Die Partition des längeren Arrays wird durch die Partition des kürzeren vollständig bestimmt. Durch Vertauschen der Eingaben, wenn len(nums1) > len(nums2) gilt, stellen wir sicher, dass das kürzere Array immer den Suchraum bildet. Die Invariante: Wenn j aus i und der Gesamtlänge abgeleitet wird, ist j immer ein gültiger Partitionsindex für 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}')Umgang mit geraden und ungeraden Gesamtlängen
Bei einer insgesamt ungeraden Länge ist der Median das Maximum der linken Hälften (max(max_left1, max_left2)). Bei einer geraden Länge ist er der Durchschnitt aus dem Maximum der linken Hälften und dem Minimum der rechten Hälften. Die Formel (m+n+1)//2 für die Größe der linken Hälfte funktioniert in beiden Fällen: Bei einer geraden Gesamtlänge ergibt sie n//2 (ein zusätzliches Element auf der linken Seite), und wir mitteln diesen Wert mit min_right, um den Median bei gerader Länge zu erhalten.
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 arraySonderfälle
Wichtige Sonderfälle: (1) Ein Array ist leer – der Median des nicht leeren Arrays. (2) Alle Elemente eines Arrays sind kleiner als die des anderen – die Partition liegt an einem äußersten Punkt. (3) Doppelte Elemente – der Algorithmus verarbeitet sie ganz natürlich. (4) Beide Arrays haben die Länge 1 – der einfache Median aus zwei Elementen. Testen Sie diese Fälle nach dem Programmieren immer. Sentinel-Werte -∞ und +∞ behandeln Randpartitionen (i=0 oder i=m) sauber.
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.5Verallgemeinerung: k-kleinstes Element in zwei Arrays
Das Medianproblem lässt sich auf das Finden des k-kleinsten Elements in zwei sortierten Arrays verallgemeinern. Vergleichen Sie in jedem Schritt das k//2-te Element jedes Arrays. Verwerfen Sie die kleinere Hälfte: Diese k//2 Elemente sind allesamt kleiner als das k-kleinste Element, daher können wir sie entfernen. Verringern Sie k um k//2 und fahren Sie rekursiv fort. Basisfälle: Ein Array ist leer (geben Sie das k-kleinste Element des verbleibenden Arrays zurück) oder k=1 (geben Sie das Minimum der beiden ersten Elemente zurück). Laufzeit: 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)}')Vergleich aller Ansätze
Abschließender Vergleich: Arrays zusammenführen: O(m+n) Zeit, O(m+n) Speicher. Binärsuche über die Partition: O(log(min(m,n))) Zeit, O(1) Speicher. Rekursion für das k-kleinste Element: O(log(m+n)) Zeit, O(log k) Aufrufstapel. Die Methode der binären Suche über die Partition ist diejenige, die Interviewer bei diesem Problem erwarten. Es ist das schwierigste verbreitete LeetCode-Problem, das sich klar erklären lässt – üben Sie die Partitionslogik und die vier Grenzprüfungen, bis sie automatisch ablaufen.
# 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')Kommunikationsstrategie im Vorstellungsgespräch
Für dieses schwierige Problem im Vorstellungsgespräch: (1) Nennen Sie sofort den naiven O(m+n)-Merge-Ansatz – das zeigt Ihre Kompetenz. (2) Erklären Sie das Ziel O(log(min(m,n))) und die Partitionsidee. (3) Gehen Sie die Partitionsinvariante durch: max_left1 ≤ min_right2 und max_left2 ≤ min_right1. (4) Behandeln Sie Sentinel-Werte explizit. (5) Nennen Sie die Medianformel für ungerade und gerade Längen. (6) Testen Sie die Lösung mit 1–2 Beispielen. Dieses 5-Schritte-Framework zeigt systematisches Problemlösen, selbst bei einem Problem, das nur wenige Kandidaten unter Druck perfekt lösen.
# 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.5Schnelltest
Testen Sie Ihr Verständnis der Konzepte aus dieser Lektion zu Data Structures & Algorithms — Coding Interview Prep.
Zusammenfassung der Lektion
In dieser Lektion haben Sie gelernt: Der Median zweier sortierter Arrays lässt sich in O(log(min(m,n))) bestimmen, indem im kürzeren Array per binärer Suche die korrekte Partitionsgrenze gesucht wird, die Partition ist gültig, wenn max_left1 ≤ min_right2 und max_left2 ≤ min_right1 gilt, wobei Sentinel-Werte Grenzfälle behandeln, und die Verallgemeinerung auf das k-kleinste Element verwendet einen rekursiven Ansatz zur schrittweisen Eliminierung der Hälfte in O(log k) Zeit. Herzlichen Glückwunsch zum Abschluss der Divide-and-Conquer-Lektionen – Sie verfügen nun über ein umfassendes Werkzeugset für Coding-Interviews!
Häufig gestellte Fragen
Ist die Lektion „Median zweier sortierter Arrays“ kostenlos?
Ja — der vollständige Text von „Median zweier sortierter Arrays“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des Coding Interview Prep-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der Coding Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „Median zweier sortierter Arrays“?
Lösen Sie median-of-two-sorted-arrays in O(log(min(m,n))) mithilfe einer binären Suche nach der Partitionsgrenze des kürzeren Arrays. Du übst Coding Interview Prep mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.
Brauche ich Erfahrung, um Coding Interview Prep zu starten?
Keine Vorkenntnisse erforderlich. Coding Interview Prep auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 4 von 4.
Wie lange dauert die Lektion „Median zweier sortierter Arrays“?
Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.
Kann ich in dieser Coding Interview Prep-Lektion Code schreiben und ausführen?
Ja. Jede Coding Interview Prep-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.
Alle Lektionen in diesem Kurs
- Divide-and-Conquer-Vorlage
- Inversionen mit modifiziertem Merge Sort zählen
- Majority Element: Boyer-Moore-Abstimmung
- Median zweier sortierter Arrays