Median_of_Two_Sorted_Arrays_Kth.cpp

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int N1 = nums1.size(), N2 = nums2.size();
        int total = N1 + N2;
        int left = (total+1)/2;
        int right = (total + 2) / 2;   
        //If the final array is odd, the median will calculate twice
        return (getKth(nums1, 0, N1, nums2, 0, N2, left) + getKth(nums1, 0, N1, nums2, 0, N2, right))/2.0;
    }
    double getKth(vector<int> &nums1, int start1, int end1, vector<int> &nums2, int start2, int end2, int k)
    {
        int len1 = end1 - start1, len2 = end2 - start2;
        if(len1>len2)
            return getKth(nums2, start2, end2, nums1, start1, end1, k);
        
        if(len1 == 0)
            return nums2[k + start2 -1];
        
        if(k == 1) return min(nums1[start1], nums2[start2]);
        
        int index1 = start1 + min(len1, k/2) - 1;
        int index2 = start2 + min(len2, k/2) - 1;
        if(nums1[index1]>nums2[index2])
            return getKth(nums1, start1,end1,nums2, index2+1, end2, k - (index2 - start2 + 1));
        else
            return getKth(nums1, index1+1, end1, nums2, start2, end2, k - (index1 - start1 + 1));
        
    }
};