Problem 18 · Binary Search

Median of Two Sorted Arrays

HardClassic DSA & systems

01Problem

Given two sorted arrays, return the median of their combined elements in O(log(min(m, n))).

02Key insight

Binary search a partition of the shorter array so the left halves of both together hold half the elements and every left element <= every right element; the median comes from the boundary values.

03Solution

solution.pypython23 lines

def find_median_sorted_arrays(a: list[int], b: list[int]) -> float:
    if len(a) > len(b):
        a, b = b, a
    m, n = len(a), len(b)
    half = (m + n + 1) // 2
    lo, hi = 0, m
    inf = float("inf")
    while lo <= hi:
        i = (lo + hi) // 2  # elements taken from a
        j = half - i        # elements taken from b
        a_left = a[i - 1] if i > 0 else -inf
        a_right = a[i] if i < m else inf
        b_left = b[j - 1] if j > 0 else -inf
        b_right = b[j] if j < n else inf
        if a_left <= b_right and b_left <= a_right:
            if (m + n) % 2:
                return float(max(a_left, b_left))
            return (max(a_left, b_left) + min(a_right, b_right)) / 2
        if a_left > b_right:
            hi = i - 1
        else:
            lo = i + 1
    raise ValueError("inputs must be sorted and non-empty overall")

Try it first.

TimeO(log min(m, n))

SpaceO(1)

tests.py · 4 passing

tests.pypython4 lines

assert find_median_sorted_arrays([1,3], [2]) == 2.0
assert find_median_sorted_arrays([1,2], [3,4]) == 2.5
assert find_median_sorted_arrays([], [1]) == 1.0
assert find_median_sorted_arrays([1,2,3,4,5], [6]) == 3.5

04Staff-level follow-up

Median across K sorted shards on different machines? Binary search on the value domain, asking each shard for count(<= x) in O(log n), so only counts cross the network; approximate alternative: t-digest/KLL sketches.