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

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

Input

A =B =

שלב 1 מתוך 6

מצא את החציון של שני מערכים ממוינים (ב־A יש 4, ב־B יש 6, סה"כ 10). A קצר יותר (4 מול 6), לכן חפש בינארית ב־A — המערך המודגש — במקום.

השוואות

חלוקות שנוסו

▶אלגוריתם

median(A, B):
S = shorter(A, B); L = longer(A, B)
lo = 0; hi = |S|; half = ⌊(m+n+1)/2⌋
while lo ≤ hi:
i = ⌊(lo+hi)/2⌋; j = half − i
if S[i−1] ≤ L[j] and L[j−1] ≤ S[i]: median
else if S[i−1] > L[j]: hi = i − 1
else: lo = i + 1

מקרא

גבול החלוקה

חצי שמאלי

איבר(י) החציון

חצי ימני

האלגוריתם מבצע חיפוש בינארי על חלוקה של המערך הקצר יותר (A ו־B שומרים על מיקומם). חלוקה תקפה כאשר כל איבר בחצי השמאלי ≤ כל איבר בחצי הימני — זמן O(log(min(m, n))).

1 / 6מהירות