4、Midian Of Two Sorted Array

输入：int nums1[1,3,5,8] int nums2[2,9,10,11]

过程：求两个排序的数组的中位数

输出：6.5

注意：数组排序方式一致，都是升序或者都是降序

算法：

• 求中位数说白了就是求特殊的第k大或者第k、k+1大的数。但是这里比较棘手的是要在两个数组中求
• 题目时间复杂度有要求log(m+n)，基本确定使用二分查找，难点就在于怎么在两个数组中实现二分查找。

思路：

基本知道求两数组中位数有以下两种情况：

• 当m+n为偶数，中位数=(数组[(m+n)/2]+数组[(m+n)/2+1])/2.0
• 当m+n奇数时，中位数=数组[(m+n)/2]

由上可知，假设m+n=k，要求的就是两个数组的第k/2大值或者第k/2+1大值，所以需要设置一个函数来求第k大值。如果数组1为空，第k大值就在数组2中，反过也是一样。如果k=1说明求的是最小值，只需返回判断数组1[0]和数组2[0]中的较小值即可。

过一遍算法：假设数组1 arr1 = [1,3,5,8] 数组 arr2 = [2,9,10,11]，这里我们知道k=4 or 5(因为合并后的长度为偶数)
先求第4大，

比较arr1[m/2]和arr2[n/2]，明显arr1[m/2]小于arr2[n/2]，所以我们知道arr[0]_{arr[m/2]都小于arr2[n/2]；所以下一步就需要把目标定在arr1[m/2+1]}arr[m-1]；
我们查找的范围缩小到arr1[m/2+1]_{arr[m/2+m/2]和arr2[0]}arr[n/2]；知道查找的范围缩小为1，就找到我们要找的第4大的值为5，
同理可求出第5大的值为8，平均值就是要求的中位数6.5

查找第k大函数如下：

int findKth(vector<int>& nums1, int m, vector<int>& nums2, int n, int k)
    {
        if (m >= nums1.size()) return nums2[n + k - 1];
        if (n >= nums2.size()) return nums1[m + k - 1];
        if (k == 1) return min(nums1[m], nums2[n]);

        int p1 = m + k / 2 - 1;
        int p2 = n + k / 2 - 1;
        int mid1 = p1 < nums1.size() ? nums1[p1] : INT_MAX;
        int mid2 = p2 < nums2.size() ? nums2[p2] : INT_MAX;
        if (mid1 < mid2)
        {
            return findKth(nums1, m + k / 2, nums2, n, k - k/2);
        }
        else
        {
            return findKth(nums1, m, nums2, n + k/2, k- k/2);
        }
    }

求中位数代码如下：

double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
       int len = nums1.size() + nums2.size();
       if (len % 2 == 0) {
           return (findKth(nums1, 0, nums2, 0, len / 2) + findKth(nums1, 0, nums2, 0, len / 2 + 1)) / 2.0;
       }
       return findKth(nums1, 0, nums2, 0, (len + 1) / 2);
   }