Median of Two Sorted Arrays
Part of Practice: Rotations & Partitions
You are given two sorted integer arrays, nums1 of length m and nums2 of length n. Return the median of all m + n numbers — the middle value if the combined length is odd, or the average of the two middle values if it is even.
The required time is O(log(m + n)), which rules out merging the arrays. Either array may be empty (but not both), and lengths go up to 1000 each.
Examples
- Input:
- nums1 = [1, 3], nums2 = [2]
- Output:
- 2.0
Merged order is [1, 2, 3]; the middle value is 2.
- Input:
- nums1 = [1, 2], nums2 = [3, 4]
- Output:
- 2.5
Merged order is [1, 2, 3, 4]; the median is (2 + 3) / 2 = 2.5.
Hints
One at a time — struggle first, peek second.
Your thinking space — verify on LeetCode, then mark it.