Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int N1 = nums1.size(), N2 = nums2.size();
if(N1 > N2)
return findMedianSortedArrays(nums2, nums1);
int iMin = 0, iMax = N1;
while(iMin <= iMax)
{
int i = (iMin + iMax) / 2;
int j = (N1 + N2 +1)/2 - i;
if(i!=N1 && j!=0 && nums2[j-1] > nums1[i])
iMin = i + 1;
else if(j!=N2 && i!=0 && 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 minRight = 0;
if(i == N1){
minRight = nums2[j];
}
else if(j == N2){
minRight = nums1[i];
}
else{
minRight = min(nums1[i], nums2[j]);
}
return (maxLeft + minRight)/2.0;
}
}
return 0;
}
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment