Title
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)).
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
//cpp:
#include<iostream>
#include<string>
#include<algorithm>
#include<unordered_set>
#include<map>
using namespace std;
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
if (nums1.size()>nums2.size()) {
swap(nums1, nums2);
}
int n1 = nums1.size();
int n2 = nums2.size();
int iMin = 0, iMax = n1;
int halfLen = (n1+n2 + 1) / 2;
while (iMin <= iMax) {
int i = (iMin + iMax) / 2;
int j = halfLen - i;
if (i < iMax&&nums2[j - 1]>nums1[i]) {
iMin = i + 1;
}
else if (i > iMin&&nums1[i - 1] > nums2[j]) {
iMax = i - 1;
}
else {
int maxleft = 0;
if (i == 0) maxleft = nums2[j - 1];
else if (j == 0) maxleft = nums1[i - 1];
else maxleft = max(nums1[i - 1], nums2[j - 1]);
if ((n1 + n2) % 2 == 1) return maxleft;
int maxright = 0;
if (i == n1) maxright = nums2[j];
else if (j == n2) maxright = nums1[i];
else maxright = min(nums1[i], nums2[j]);
return (maxleft + maxright) / 2.0;
}
}
}
};
int main()
{
Solution a1;
vector<int> v = { 1,2,3,3,3,4,5 };
vector<int> a = { 1,1 };
vector<int> b = { 1,2 };
cout << a1.findMedianSortedArrays(a, b) << endl;
return 0;
}