Median of Two Sorted Arrays
Given two sorted arrays nums1 and nums2 of size m and n, return the median of the two arrays combined.
Example 1
The merged array is [1, 2, 3], whose median is 2.
Example 2
The merged array is [1, 2, 3, 4], whose median is (2 + 3) / 2 = 2.5.
Merging the two arrays and picking the middle is O(m + n) and will pass. The intended solution runs in O(log(min(m, n))) by binary searching for the partition that splits both arrays into a correct left and right half.
Either array may be empty, but never both.
Examples
Example 1
- Input:
- [1,3], [2]
- Output:
- 2
Merged: [1,2,3]. The middle element is 2.
Example 2
- Input:
- [1,2], [3,4]
- Output:
- 2.5
Merged: [1,2,3,4]. With an even count the median is the average of the two middle values, (2+3)/2 = 2.5.
Example 3
- Input:
- [], [1]
- Output:
- 1
One array may be empty; the median is then just the median of the other.
Constraints
nums1.length == m,nums2.length == n0 <= m <= 1000,0 <= n <= 1000,1 <= m + n-10^6 <= nums1[i], nums2[i] <= 10^6- Both arrays are sorted in non-decreasing order.
Run checks your code against the 3 examples. Submit checks it against all 303 tests and needs a free account. You can also try ideas in the free JavaScript or Python compiler.