4. Median of Two Sorted Arrays
1. Description
Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.
The overall run time complexity should be O(log (m+n)).
2. Example
Example 1
Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
Explanation: merged array = [1,2,3] and median is 2.
Example 2
Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000
Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.
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$
4. Solutions
Binary Search
m = nums1.size(), n = nums2.size()
Time complexity: O(logmin(m, n))
Space complexity: O(1)
class Solution {
public:
double findMedianSortedArrays(const vector<int> &nums1, const vector<int> &nums2) {
const int m = nums1.size(), n = nums2.size();
if (m > n) {
return findMedianSortedArrays(nums2, nums1);
}
int left = 0, right = m;
double result = 0;
while (left <= right) {
int nums1_left_count = left + (right - left) / 2;
int nums2_left_count = (m + n + 1) / 2 - nums1_left_count;
int nums1_left_value =
nums1_left_count == 0 ? numeric_limits<int>::min() : nums1[nums1_left_count - 1];
int nums1_right_value =
nums1_left_count == m ? numeric_limits<int>::max() : nums1[nums1_left_count];
int nums2_left_value =
nums2_left_count == 0 ? numeric_limits<int>::min() : nums2[nums2_left_count - 1];
int nums2_right_value =
nums2_left_count == n ? numeric_limits<int>::max() : nums2[nums2_left_count];
if (nums1_left_value > nums2_right_value) {
right = nums1_left_count - 1;
} else if (nums2_left_value > nums1_right_value) {
left = nums1_left_count + 1;
} else {
if ((m + n) % 2 == 1) {
result = max(nums1_left_value, nums2_left_value);
} else {
result = (static_cast<double>(max(nums1_left_value, nums2_left_value)) +
static_cast<double>(min(nums1_right_value, nums2_right_value))) /
2.0;
}
break;
}
}
return result;
}
};