There are two sorted arrays nums1 and nums2 of size m and n respectively.
Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
You may assume nums1 and nums2 cannot be both empty.
Example 1:
nums1 = [1, 3]
nums2 = [2]
The median is 2.0
Example 2:
nums1 = [1, 2]
nums2 = [3, 4]
The median is (2 + 3)/2 = 2.5
Solution:
Define a k-th helper function:
We want to find a block such that l1[0…i] and l2[0…k-i-2] are the k smallest elements. Which means i is the smallest such that l1[i] > l2[k-i-1]. And the rest are routines.
class Solution {
public:
int n;
int m;
int kth(vector<int>& l1, vector<int>& l2, int k){
k--;
int l = -1, r = n-1;
while(l<=r){
int i = (l+r)/2;
int j = (k-i-1);
if(j < 0){
r = i-1;
continue;
}
if(i<0 || j>m-1 || l1[i] <= l2[j]){
l = i+1;
}
else{
r = i-1;
}
}
if(r+1 > n-1 || r+1 < 0) return l2[k-r-1];
if(k-r-1 > m-1 || k-r-1 < 0) return l1[r+1];
else return min(l1[r+1],l2[k-r-1]);
}
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
n = nums1.size();
m = nums2.size();
if((n+m)%2){
return (double) kth(nums1,nums2,(n+m)/2+1);
}
else{
return ((double) kth(nums1,nums2,(n+m)/2) + (double) kth(nums1,nums2,(n+m)/2+1))/2;
}
}
};