Median of Two Sorted Arrays
Return the median of two sorted arrays in O(log(min(n,m))).
Open on LeetCode ↗Intuition
The median splits the union into equal halves. So find a cut of A and a cut of B whose left parts together hold half the elements, with everything left of the cuts ≤ everything right. Binary search where to cut A — B's cut is then forced.
When a problem demands better than O(n) on sorted input, you're binary searching something — and it isn't always the answer directly. Here you search over the partition point: how many elements of the smaller array fall on the left side. The median only needs the four values straddling that cut, never the merged array itself. Binary-searching a decision rather than a value is the move that also cracks split-array-largest-sum and koko-eating-bananas.
Approach
Cut both arrays
Cut A at i and B at j with i + j = (n+m+1)//2. Left halves combined = half the union (the +1 favours the left for odd totals).
Valid cut condition
Need A[i−1] ≤ B[j] and B[j−1] ≤ A[i] (±∞ sentinels at the edges). If A[i−1] > B[j], the cut in A is too far right — move left.
Read off the median
Odd total: max of the left halves. Even: average of max(left) and min(right). Search only the shorter array for O(log min(n,m)).
Solution & live demo
Common pitfalls
Binary searching the larger array
lo, hi = 0, len(b)
if len(a) > len(b): a, b = b, a lo, hi = 0, len(a)
j = half - i can then fall outside the other array's bounds, producing negative or oversized indices. Searching the shorter side keeps j legal for every i and pins the complexity to O(log min(m, n)).
Guarding the edges with real array values
a_left = a[i-1] if i > 0 else a[0]
a_left = a[i-1] if i > 0 else -INF
An empty left partition must never lose a comparison, and an empty right partition must never win one — that's precisely what the infinities encode. Substituting a real element makes the cut appear invalid and the search never converges.
Integer division on the final average
return (max(a_left, b_left) + min(a_right, b_right)) // 2
return (max(a_left, b_left) + min(a_right, b_right)) / 2
The median of an even-length set is genuinely fractional — [1, 2, 3, 4] gives 2.5. Floor division truncates it to 2.
Edge cases
Cut takes 0 from it; sentinels handle every comparison — median of the other array.
Search pushes i to n; sentinel +∞ on A's right keeps checks valid.