Median of Two Sorted Arrays
Given two sorted arrays nums1 and nums2 of sizes m and n, return the median of the two sorted arrays combined.
The median is the middle value in the sorted order of all elements. If the total number of elements is even, the median is the average of the two middle values.
Your solution must run in O(log(m + n)) time.
Example 1
Input
nums1 = [1,3], nums2 = [2]Output
2The merged sorted array is [1, 2, 3], so the middle value is 2.
Example 2
Input
nums1 = [1,2], nums2 = [3,4]Output
2.5The merged sorted array is [1, 2, 3, 4], so the median is the average of 2 and 3.
Constraints
- nums1.length == m
- nums2.length == n
- 0 <= m <= 1000
- 0 <= n <= 1000
- 1 <= m + n <= 2000
- -10^6 <= nums1[i], nums2[i] <= 10^6
- Both
nums1andnums2are sorted in non-decreasing order.