LeetCode 4.寻找两个有序数组的中位数

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。
请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
你可以假设 nums1 和 nums2 不会同时为空。

示例 1:

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

则中位数是 2.0

示例 2:

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

则中位数是 (2 + 3)/2 = 2.5

简单解析：最重要的就是求两个有序数组中的第k大，有几个小细节注意一下就行了。
如，求两个有序数组$A$和$B$的第$K$大的数，那么将$A$和$B$的前$\frac{K}{2}$的数组分别切割出来，比较$A[\frac{K}{2}]$和$B[\frac{K}{2}]$的大小就可以消去$\frac{K}{2}$个数，为什么那？因为如果$A[\frac{K}{2}]<B[\frac{K}{2}]$，那么$A[0:\frac{K}{2}]$肯定都小于$B[\frac{K}{2}]$（废话），所以接下来只需要在剩下的数中找第$\frac{K}{2}$大的数就行了（一些细节没描述），详见代码。
时间复杂度：$O(log_{2}{(len(A)+len(B)}))$

class Solution {
public:
    double findkth(vector<int>& nums1, vector<int>& nums2, int l1, int r1, int l2, int r2, int k) {
        if (l1 > r1) return nums2[l2 + k -1]; // 如果nums1空了，return nums2的第k个，下同理
        if (l2 > r2) return nums1[l1 + k -1];
        if (k == 1) return min(nums1[l1], nums2[l2]); // 因为最后一次比较后肯定是前k个比较完了，l1和r1一个是在前k个，一个不是
                                                        // 前k个，答案是第k个，是小的那个，所以取min()
        int mid = k / 2; // 如果是奇数就向下取整
        int new1 = l1 + mid - 1, new2 = l2 + mid -1;
        if (new1 > r1) new1 = r1; // 当溢出时让new1=r1，不影响结果，只是令log2不太log2而已
        if (new2 > r2) new2 = r2;
        if (nums1[new1] < nums2[new2]) {
            return findkth(nums1, nums2, new1 + 1, r1, l2, r2, k - (new1 - l1 + 1));
        } else {
            return findkth(nums1, nums2, l1, r1, new2 + 1, r2, k - (new2 - l2 + 1));
        }
    }
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int len1 = nums1.size(), len2 = nums2.size();
        if ((len1 + len2) & 1) {
            return findkth(nums1, nums2, 0, len1 - 1, 0, len2 - 1, (len1 + len2 + 1) / 2);
        }
        double ans = findkth(nums1, nums2, 0, len1 - 1, 0, len2 - 1, (len1 + len2) / 2);
        ans += findkth(nums1, nums2, 0, len1 - 1, 0, len2 - 1, (len1 + len2) / 2 + 1);
        ans /= 2;
        return ans;
    }
};