Median of Two Sorted Arrays

Problem

You are given two arrays nums1 and nums2, each sorted in ascending order, of sizes m and n. Return the median of all m + n values taken together. If the combined count is even, the median is the mean of the two middle values. Aim for logarithmic time; the linear merge is the baseline, not the target.

• Each array has at most 5,000 elements. Either array may be empty, but not both.
• Values are integers between -1,000,000,000 and 1,000,000,000.

Examples

• nums1 = [4, 9, 15], nums2 = [6, 11] → 9.0. Merged: [4, 6, 9, 11, 15], middle value 9.
• nums1 = [2, 8, 20, 25], nums2 = [5, 30] → 14.0. Merged: [2, 5, 8, 20, 25, 30], mean of 8 and 20.
• nums1 = [], nums2 = [42] → 42.0. One array empty; the other's median is the answer.

Hints

1. The median splits the combined data into a left half and a right half of known sizes. Think about how many elements of that left half come from nums1.
2. If you take i elements from nums1 for the left half, the number from nums2 is forced. What must be true of the four values at the two cut points for the split to be a valid "everything on the left <= everything on the right"?
3. Binary search on i over the shorter array; when the cut is invalid, the direction of the violation tells you which way to move.