class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int len1 = nums1.size(), len2 = nums2.size(), k = (len1 + len2 + 1) / 2;
        if((len1 + len2) % 2)
            return findKth(nums1, nums2, 0, 0, k);
        else
            return (findKth(nums1, nums2, 0, 0, k) + findKth(nums1, nums2, 0, 0, k + 1)) / 2.0;
    }

private:
    int findKth(vector<int>& nums1, vector<int>& nums2, int lo1, int lo2, int k)
    {
        int len1 = static_cast<int>(nums1.size()) - lo1, len2 = static_cast<int>(nums2.size()) - lo2;
        if(len1 > len2)
            return findKth(nums2, nums1, lo2, lo1, k);

        if(!len1)return nums2[lo2 + k - 1];
        if(k == 1)return min(nums1[lo1], nums2[lo2]);

        int i = min(k / 2, len1), j = k - i;
        if(nums1[lo1 + i - 1] >= nums2[lo2 + j - 1])
            return findKth(nums1, nums2, lo1, lo2 + j, k - j);
        else
            return findKth(nums1, nums2, lo1 + i, lo2, k - i);

    }
};