Median of Two Sorted Arrays

Median of Two Sorted Arrays is a classic that looks like it wants you to merge two arrays — and then surprises you by demanding O(log(m + n)). The real move is to stop thinking about merging and start thinking about a single balanced cut.

The slow way first

The obvious idea: merge A and B into one sorted array, then pick the middle. That is correct and easy, but merging is O(m + n) — you touch every element. The problem explicitly asks for a logarithmic solution, so a full merge is too slow.

The question to ask: do I even need the whole merged array? The median only depends on the few values around the middle. If I can place a single cut that splits the combined order into a left half and a right half of equal size, I can read the median straight off the border — no merge required.

The idea

Imagine cutting both arrays so that all the values on the left are smaller than all the values on the right, and the left half holds exactly half = (m + n + 1) // 2 values. We binary-search the cut position on the smaller array; the cut on the other array is then forced, because the two left counts must add up to half.

A cut is valid when the largest value left of either cut is no bigger than the smallest value right of the other cut: maxLeftA <= minRightB and maxLeftB <= minRightA. If A's left edge is too big we slide the cut left; if it is too small we slide right — exactly a binary search.

Walk through it

Step through the animation. A = [1, 3] is the smaller array, so we search it; B = [2]. The total length is 3, so half = (2 + 1 + 1) // 2 = 2 values must land on the left.

We guess i = 1: take one value from A on the left, which forces j = half − i = 1 value from B. The four border values are maxLeftA = 1, minRightA = 3, maxLeftB = 2, minRightB = +inf. Check validity: 1 <= +inf and 2 <= 3 both hold, so the cut is balanced — left half {1, 2}, right half {3}. The merged order is [1, 2, 3], and the single middle value is 2, so the median is 2.0.

Pseudocode

make sure A is the shorter array (swap if needed)
half = (len(A) + len(B) + 1) // 2
binary-search a cut i on A, lo = 0, hi = len(A):
    i = midpoint of lo..hi          # values from A on the left
    j = half - i                    # forced values from B on the left
    maxLeftA / minRightA  = border values around i (use +-inf at the ends)
    maxLeftB / minRightB  = border values around j (use +-inf at the ends)
    if maxLeftA <= minRightB and maxLeftB <= minRightA:
        valid cut -> read the median off the four borders
    elif maxLeftA > minRightB:
        hi = i - 1                  # A's left is too big, cut earlier
    else:
        lo = i + 1                  # A's left is too small, cut later

The Python solution

def find_median(A, B):
    if len(A) > len(B):
        A, B = B, A          # search the smaller array
    m, n = len(A), len(B)
    half = (m + n + 1) // 2
    lo, hi = 0, m
    while lo <= hi:
        i = (lo + hi) // 2   # cut in A
        j = half - i         # matching cut in B
        INF = float("inf")
        maxLA = -INF if i == 0 else A[i - 1]
        minRA = INF if i == m else A[i]
        maxLB = -INF if j == 0 else B[j - 1]
        minRB = INF if j == n else B[j]
        if maxLA <= minRB and maxLB <= minRA:
            if (m + n) % 2:  # odd total
                return float(max(maxLA, maxLB))
            return (max(maxLA, maxLB) + min(minRA, minRB)) / 2
        elif maxLA > minRB:
            hi = i - 1
        else:
            lo = i + 1

• We first swap so A is the shorter array — that keeps the search space O(min(m, n)).
• half is how many values must end up on the left of the combined cut; the + 1 makes the odd case put the extra element on the left.
• i is the binary-search guess: how many of A's values go left. j = half - i is then forced so the two left counts sum to half.
• maxLA, minRA, maxLB, minRB are the four border values around the two cuts; the -inf/+inf guards handle an empty side at an array edge.
• Line 16 is the validity test: a good cut has every left value <= every right value. When it holds, the odd case returns the larger left border, and the even case averages the larger left and the smaller right.
• If maxLA > minRB, A's left side reaches too high, so we move the cut earlier (hi = i - 1); otherwise we move it later (lo = i + 1).

Complexity

By searching the cut on the smaller array, each iteration halves the candidate positions, so the work is logarithmic in the shorter length. We never build a merged array, so the extra space is O(1).

When this pattern shows up

Practice