找两个升序数组的中位数

LeetCode 4 ： 找两个升序数组的中位数(第 k 小)

solution：每次删一半

int getkth(int l1, int l2, vector<int> &nums1, vector<int> &nums2, int k)
    {
        if(l1 == nums1.size()) return nums2[l2 + k - 1];
        if(l2 == nums2.size()) return nums1[l1 + k - 1];
        if(k == 1) return min(nums1[l1], nums2[l2]);
        int mid = k / 2;

        int r1 = min(nums1.size() - 1, l1 + mid - 1);
        int r2 = min(nums2.size() - 1, l2 + mid - 1);
        if(nums1[r1] <= nums2[r2]) return getkth(r1 + 1, l2, nums1, nums2, k - (r1 - l1 + 1));
        return getkth(l1, r2 + 1, nums1, nums2, k - (r2 - l2 + 1));
    }
    
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int totlen = nums1.size() + nums2.size(); 
        if((totlen) & 1) 
            return getkth(0, 0, nums1, nums2, totlen / 2 + 1);
        return (getkth(0, 0, nums1, nums2, totlen / 2) + getkth(0, 0, nums1, nums2, totlen / 2 + 1)) / 2.0;
    }