Median of Two Sorted Arrays — Step-by-Step Visualization

Algorithm Pattern

Binary Search on Partition

Key Idea

Instead of merging, binary search for the partition index i in the smaller array. The matching partition j in the larger array is forced by the total half-length.

Step-by-Step Approach

1. Always binary search on the smaller array A (swap if needed). This keeps i in-bounds.
2. i partitions A into left=[0..i] right=[i+1..]. j = half - i - 2 partitions B the same way, so both halves combined have exactly ⌊(m+n)/2⌋ elements.
3. Valid partition when Aleft ≤ Bright AND Bleft ≤ Aright. If Aleft > Bright, move i left (hi = i−1). If Bleft > Aright, move i right (lo = i+1).
4. Once valid: odd total → median = min(Aright, Bright). Even total → (max(Aleft, Bleft) + min(Aright, Bright)) / 2.
5. Handle out-of-bounds with −∞ / +∞ sentinels (empty left = −∞, empty right = +∞).

Common Gotchas

• Swap so A is always the shorter array — otherwise j can go negative.
• lo, hi = 0, len(A)−1 (index-based). i = (lo+hi)//2 picks the last element of A's left partition.
• j = half − i − 2 can be −1 (B's left partition is empty) — guard with `if j >= 0`.