Median of two sorted arrays

Given two sorted arrays of sizes m and n, return the median of all their elements combined, in O(log(m + n)) time.

Before you code

Merging is O(m + n). Instead, search for a way to cut both arrays so that the left pieces together hold half of all the elements and every element on the left is ≤ every element on the right. Choosing the cut in the shorter array fixes the cut in the other.

Hints

1. Binary search the cut i in the shorter array, from 0 to its length; then j = (m + n + 1) // 2 - i.
2. The cut is right when A[i-1] <= B[j] and B[j-1] <= A[i], treating out-of-range values as minus or plus infinity.
3. If A[i-1] > B[j], cut A further left; otherwise further right.
4. The median comes from the largest left value and, for even totals, the smallest right value.

Production & complexity notes

When solving Median of two sorted arrays on LeetCode (hard), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Searching an answer space to reinforce the underlying pattern.

What it practices

Binary search over an answer that isn't an index into either array, from Searching an answer space.