Median of Two Sorted Array

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

Idea:

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);

    }
};