הפרד ומשול

חציון של שני מערכים ממוינים

מוצא את החציון של שני מערכים ממוינים בזמן O(log n) בעזרת חיפוש בינארי.

שלב 1 מתוך 3

מצא את החציון של שני מערכים ממוינים באורכים 5 ו־6. חיפוש בינארי על המערך הקצר יותר כדי למצוא את החלוקה הנכונה.

▶אלגוריתם
Median(A, B):
ensure len(A) ≤ len(B)
lo = 0; hi = len(A)
while lo ≤ hi:
i = (lo+hi)/2; j = (m+n+1)/2 − i
if valid partition: compute median
if A[i−1] > B[j]: hi = i−1
else: lo = i+1

איך זה עובד

חיפוש בינארי על המערך הקצר יותר כדי למצוא את החלוקה i. אז j = (m+n+1)/2 − i. חלוקה תקפה מקיימת A[i−1] ≤ B[j] ו־B[j−1] ≤ A[i]. זמן O(log(min(m,n))).

מערך A
שמאל→
1
0
3
1
8
2
9
3
15
4
←ימין
מערך B
שמאל→
7
0
11
1
18
2
19
3
21
4
25
5
←ימין
חיפוש בינארי על A: lo = 0, hi = 5
גבול החלוקה
חצי שמאלי
1 / 3מהירות