Median of Two Sorted Arrays

Finds the median of two sorted arrays in O(log(min(m,n))) by binary-searching a partition of the shorter array.

Input

A =B =

Step 1 of 6

Find the median of two sorted arrays (A has 4, B has 6, total 10). A is shorter (4 vs 6), so binary-search A — the highlighted array — in place.

Comparisons

Partitions tried

▶Algorithm

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

Legend

Partition boundary

Left half

Median element(s)

Right half

The algorithm binary-searches a partition of whichever array is shorter (A and B keep their positions). A partition is valid when every left-half element is ≤ every right-half element — O(log(min(m, n))) time.

1 / 6Speed