Median of Two Sorted Arrays in O(log(min(n, m)))

Two sorted arrays, one median. Merging them and indexing the middle is O(n + m) and takes about four lines. This page is about the O(log(min(n, m))) solution, which is the reason the problem is rated the way it is.

The interesting part is not the binary search itself. It is what you binary search over: not a value, but a place to cut.

What the median actually requires

Forget merging. A median is defined by a property: it sits at the point where half the combined elements are below and half above. So instead of producing the merged array, produce the boundary it would have.

Cut array a somewhere, putting i elements on the left. Cut array b somewhere, putting j on the left. The cut is the one we want when both hold:

1. The left parts together hold half the elements: i + j = (n + m + 1) / 2.
2. Nothing on the left exceeds anything on the right: a[i-1] <= b[j] and b[j-1] <= a[i].

The first condition is the crucial one for efficiency. It means j is not a free choice — it is (n + m + 1) / 2 - i. There is only one number to search for, and that is what makes a binary search possible at all.

Searching the cut

Binary search i over [0, n] — note the range includes both ends, since cutting before everything or after everything are legitimate. For each candidate, derive j and check the two cross conditions:

• If a[i-1] > b[j], too many elements of a are on the left. Move the cut left: high = i - 1.
• If b[j-1] > a[i], too few. Move the cut right: low = i + 1.
• Otherwise the cut is valid and the answer reads straight off it.

Search the shorter array. If a is the longer one, a valid i can force j outside the bounds of b — negative, or past its end. Swapping so a is never longer guarantees j stays in range, and as a bonus makes the complexity depend on the smaller length.

The sentinels are the whole trick

At i = 0 there is no a[i-1]. At i = n there is no a[i]. The same holds for b. Written as special cases, that is four branches multiplied by the two parity cases, and it is where most implementations go wrong.

Instead, define the missing neighbours as infinities:

An empty a now needs no code of its own: n = 0, the search range is [0, 0], i = 0, both of a's neighbours are infinities, and the answer falls out of b alone.

Walking through an example

a = [1, 3, 8], b = [7, 9, 10, 11]. Total 7, so half = 4 and the median is the largest left-hand value.

The code

def find_median(a, b):
    # Search the shorter array so the forced cut j always lands inside b.
    if len(a) > len(b):
        a, b = b, a

    n, m = len(a), len(b)
    half = (n + m + 1) // 2      # +1 leaves the odd extra on the left
    low, high = 0, n             # inclusive: cutting at either end is legal

    while low <= high:
        i = (low + high) // 2    # a[:i] goes left
        j = half - i             # forced by the half-size rule

        # Sentinels remove every empty-array and end-of-array special case.
        a_left = a[i - 1] if i > 0 else float('-inf')
        a_right = a[i] if i < n else float('inf')
        b_left = b[j - 1] if j > 0 else float('-inf')
        b_right = b[j] if j < m else float('inf')

        if a_left <= b_right and b_left <= a_right:
            if (n + m) % 2 == 1:
                return float(max(a_left, b_left))
            return (max(a_left, b_left) + min(a_right, b_right)) / 2.0

        if a_left > b_right:
            high = i - 1         # too many of a on the left
        else:
            low = i + 1

    return 0.0                   # unreachable for valid input

Complexity

The loop halves the candidate range for i each iteration and i ranges over the shorter array, so it runs log(min(n, m)) times with constant work inside. Nothing is copied, so the extra space is a handful of variables.

The mistakes that actually happen

• Not swapping so the shorter array is searched. j then goes out of bounds, usually on lopsided inputs like a length-1 array against a length-10 one.
• Using < instead of <= in the cross conditions. With many equal values several cuts are valid; a strict comparison rejects them all and the search runs off the end.
• Searching over [0, n-1] instead of [0, n]. Cutting after every element of a is a legal partition and is exactly what an empty or entirely-smaller a requires.
• Special-casing empty arrays by hand instead of using sentinels. It works, but it is four branches that the infinities give you for free.
• Returning an integer. With an even total the median can be a half-integer, so the return type has to be floating point.