给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (m+n)) 。
class Solution {
public:
double findMedianSortedArrays(vector& nums1, vector& 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 &nums1, int i, vector & 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，返回。注意边缘条件的处理
