4、求两个数组的中位数

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O(log (m+n)) 。

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
         int m = nums1.size(), n = nums2.size(), left = (m + n + 1) / 2, right = (m + n + 2)/2;
         return (findKeyValue(nums1, 0, nums2, 0, left) + findKeyValue(nums1, 0, nums2, 0, right)) / 2.0; 
    }
    int findKeyValue( vector<int> &nums1, int i, vector<int> & nums2, int j, int k) {
        if(i >= nums1.size()) return nums2[j + k - 1];
        if(j >= nums2.size()) return nums1[i + k - 1];
        if (k == 1) return min(nums1[i], nums2[j]);

        int midValue1 = ((i + k/2 -1) < nums1.size()) ? nums1[i + k/2 - 1]:INT_MAX;
        int midValue2 = ((j + k/2 -1) < nums2.size()) ? nums2[j + k/2 - 1]:INT_MAX;
        if (midValue1 < midValue2) {
            return findKeyValue(nums1, i + k /2, nums2, j,k - k/2);
        } else {
            return findKeyValue(nums1, i, nums2, j + k/2, k - k/2);
        }
    }
};

以下注意点：
1、findMedianSortedArrays函数return值需要除以2.0，而不是2.自己第一次在这里写错导致结果错误，会先转换为int，再转double。
2、寻找中位数方法：两个有序数组的长度分别为m和n，分别找(m+n+1)/2和(m+n+2)/2个，然后求平均值即可，这对奇偶都使用。若m+n为奇数的话，那么其实(m+n+1)/2和(m+n+2)/2的值相等，详单与两个相同的数字相加再除以2，还是其本身
3、对K进行二分，直到K = 1，返回。注意边缘条件的处理