Finds the median of two sorted arrays in O(log n) via binary search.
Step 1 of 3
Find the median of two sorted arrays of lengths 5 and 6. Binary search on the shorter array to find the correct partition.
▶Algorithm
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
How It Works
Binary search on the shorter array to find partition i. Then j = (m+n+1)/2 − i. A valid partition satisfies A[i−1] ≤ B[j] and B[j−1] ≤ A[i]. O(log(min(m,n))) time.