Median of two sorted arrays

Problem Given two sorted arrays, find the median of their combined order. Provide both an O(m+n) and an O(log(min(m,n))) solution.

Input / Output

• Input: sorted int arrays nums1, nums2.
• Output: median (double for even totals).

Constraints

• m + n up to 2*10^6 in the classic constraints; the binary-search solution is the differentiator.

Example

• [1,3] and [2] → 2.0; [1,2] and [3,4] → 2.5.

Expected approach

• O(m+n): two-pointer merge, stopping at the middle (O(1) space if only two values are tracked).
• O(log min): binary-search the partition of the shorter array — cut i in nums1, j = (m+n+1)/2 − i in nums2, so that max(left parts) <= min(right parts); adjust i by halving; median from the four border values; ±∞ sentinels for empty sides. Explaining the partition invariant clearly is the real test.