Median of Two Sorted Arrays

Problem

Telemetry dashboards merge two sorted metric streams of different lengths and must report the median latency without materializing the merge. Given two sorted arrays of integers, return the median of the combined sorted sequence. The catch: O(log(min(m, n))) time, which rules out any actual merge.

Example 1:

Input: a = [2, 7, 11], b = [3, 5, 9, 13]
Output: 7.0
Explanation: merged, the seven values are [2, 3, 5, 7, 9, 11, 13]; the middle element is 7.

Example 2:

Input: a = [4, 12], b = [1, 3, 6, 8, 10]
Output: 6.0
Explanation: the merged sequence [1, 3, 4, 6, 8, 10, 12] has seven elements; the median is the 4th, which is 6.

Example 3:

Input: a = [], b = [2, 4, 6]
Output: 4.0
Explanation: one stream is empty, so the median is simply the middle of the other.

Constraints:

• 0 <= m, n <= 10^4
• 1 <= m + n
• Both arrays are sorted in non-decreasing order.
• -10^6 <= a[i], b[i] <= 10^6

Solution Breakdown

Approach - binary search the cut position of the smaller array; the other cut is forced, and the median reads off four boundary values.

The median splits the (imaginary) merged sequence into a left half and a right half - left gets the extra element when the total is odd - such that every left value is at most every right value. Since only where the two cuts fall determines the middle of the merge, you never build the merge: cut a at index i (its first i elements go left) and the left half must hold half = (m + n + 1) // 2 elements total, so the cut in b is forced to j = half - i. Searching over i in [0, m] therefore searches all valid splits - and keeping a the shorter array guarantees j stays in range for every candidate i.

Each candidate is checked with four reads: a_left = a[i-1] (last of a on the left), a_right = a[i] (first of a on the right), and the matching b_left, b_right. Out-of-range sides read as -/+ infinity, which makes empty-half partitions pass naturally instead of crashing. The split is valid exactly when a_left <= b_right and b_left <= a_right - each array's left block is at most the other's right block. If a_left > b_right, too much of a sits on the left, so move hi down; if b_left > a_right, too little, move lo up. On a valid split, an odd total's median is max(a_left, b_left) (the left half holds one more, so its max is the merged middle); an even total's median is the average of max(a_left, b_left) and min(a_right, b_right). Trace a = [2, 7, 11], b = [3, 5, 9, 13]: half = 4; i = 1, j = 3 fails (b_left = 9 > a_right = 7), i = 2, j = 2 passes (7 <= 9, 5 <= 11) - odd total, median max(7, 5) = 7.0.

Edge cases - an empty array reduces the search range to [0, 0] and the sentinels carry the checks, so [] with [2, 4, 6] returns 4.0; cuts at i = 0 or i = m (one array entirely on one side) are just sentinel-protected boundary partitions; equal elements across the arrays satisfy <= cleanly.

Complexity - O(log(min(m, n))) time, O(1) space - the binary search runs over the smaller array's m + 1 cut positions with constant work per step, and nothing is materialized.