4. Median of Two Sorted Arrays
You are given two arrays, nums1 and nums2, each already sorted in non-decreasing order. Conceptually merge them into one sorted sequence and return the median of that combined sequence.
If the combined length is odd, the median is the single middle value. If it is even, the median is the average of the two middle values. Either input array may be empty, but at least one is non-empty overall.
Return the median as a real number, printed with exactly five digits after the decimal point (for example 2.00000 or 2.50000).
The classic follow-up: can you do it in O(log(m + n)) time?
Example 1:
Input: nums1 = [1, 3], nums2 = [2]
Output: 2.00000
Explanation: The merged array is [1, 2, 3]. The total length is odd, so the median is the middle value 2, printed as 2.00000.
Example 2:
Input: nums1 = [1, 2], nums2 = [3, 4]
Output: 2.50000
Explanation: The merged array is [1, 2, 3, 4]. The total length is even, so the median is the average of the two middle values (2 + 3) / 2 = 2.5, printed as 2.50000.
Constraints:
- nums1.length == m
- nums2.length == n
- 0 ≤ m ≤ 1000
- 0 ≤ n ≤ 1000
- 1 ≤ m + n ≤ 2000
- -10⁶ ≤ nums1[i], nums2[i] ≤ 10⁶
- Both arrays are sorted in non-decreasing order.
Hints:
Both arrays are already sorted, merging them into one sorted array takes only O(m + n), after which the median is a direct index lookup.
You do not need the full merged array, only the two values around the midpoint. Try partitioning both arrays so the left halves together hold the first half of all elements.
Binary-search the cut position in the SHORTER array, the cut in the other array is then forced. A valid cut satisfies aLeft <= bRight and bLeft <= aRight.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: nums1 = [1, 3], nums2 = [2]
Expected output: 2.00000