LeetCode #4

# Description:

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:

``````nums1 = [1, 3]
nums2 = [2]

The median is 2.0
``````
``````nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5
``````

# Code:

``````class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int k = nums1.size() + nums2.size();

if( k%2 == 1) {
return findKthSortedArrays(nums1.begin(), nums1.size(), nums2.begin(), nums2.size(), k/2+1 );
}
else{
return (findKthSortedArrays(nums1.begin(), nums1.size(), nums2.begin(), nums2.size(), k/2 ) +
findKthSortedArrays(nums1.begin(), nums1.size(), nums2.begin(), nums2.size(), k/2+1 )) / 2.0;
}

}

double findKthSortedArrays(vector<int>::iterator itm, int m, vector<int>::iterator itn, int n, int k ){
if(m>n) return findKthSortedArrays(itn, n, itm, m, k );
if(m==0) return *(itn + k-1);
if(k==1) return min(*itm, *itn);

int im = min(m, k/2);
int in = k-im;
if(*(itm + im -1)<*(itn + in -1))
return findKthSortedArrays(itm+im, m-im, itn, n, k-im);
else if(*(itm + im -1)>*(itn + in -1))
return findKthSortedArrays(itm, m, itn+in, n-in, k-in);
else
return *(itm + im -1);

}
};
``````