【二分查找】4. 寻找两个正序数组的中位数

4. 寻找两个正序数组的中位数（困难难度）

题目描述

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。算法的时间复杂度应该为 O(log (m+n)) 。

示例 1：

输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2

示例 2：

输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

题目分析

中位数是有序数组中可以把所有元素左右等分的一个元素，

如果数组元素是奇数个，正好是中间位置的元素；

如果数组元素是偶数个，则是中间2个元素的均值；

该题目给出了两个有序数组，求两个有序数组合并后的中位数。

1、合并两个有序数组

 一个自然的思路是：合并两个有序数组为一个有序数组，然后通过有序数组的下标计算中间位置找到中位数。该算法需要全部遍历一遍两个有序数组，其时间复杂度和空间复杂度都是O(m+n)。

虽然可以提交本题，但是不符合题目要求的时间复杂度。

/*中位数是有序数组中可以把所有元素左右等分的一个元素，
    如果数组元素是奇数个，正好是中间位置的元素；
    如果数组元素是偶数个，则是中间2个元素的均值；
    一个自然的思路是：合并两个有序数组为一个有序数组，然后通过有序数组的下标计算中间位置
    该算法的思路是O(m+n)*/
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int m=nums1.size();
        int n=nums2.size();
        int len=m+n;
        vector<int> res(len);
        int i=0,j=0,k=0;
        while(i<m&&j<n){
            if(nums1[i]<=nums2[j]) res[k++]=nums1[i++];
            else res[k++]=nums2[j++];
        }
        while(i<m) res[k++]=nums1[i++];
        while(j<n) res[k++]=nums2[j++];
        if(len%2!=0) return (double)res[len/2.0];
        else{
            double mean=(res[len/2.0]+res[len/2.0-1])/2.0;
            return mean;
        }
    }

在上述代码中，我们对求中位数的情况作了讨论：

如果数组元素是奇数个，正好是中间位置的元素；

如果数组元素是偶数个，则是中间2个元素的均值；

为了简化代码，我们可以使用一个小技巧：

分别找第 (len+1) / 2 个和 (len+2) / 2 个元素的值，然后求其平均值即可，这对奇偶数均适用。

假如len为奇数的话，那么其实 (len+1) / 2 和 (len+2) / 2 的值相等，相当于两个相同的数字相加再除以2，还是其本身。

代码实现也很简单：

// 一种统一处理中位数的技巧
int left=(len+1)/2;
int right=(len+2)/2;
// 从两个有序数组中查找第left大和第right大的数
double mean=(res[left-1]+res[right-1])/2.0;
return mean;

所以我们的代码可以修改为：

double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int m=nums1.size();
        int n=nums2.size();
        int len=m+n;
        vector<int> res(len);
        int i=0,j=0,k=0;
        while(i<m&&j<n){
            if(nums1[i]<=nums2[j]) res[k++]=nums1[i++];
            else res[k++]=nums2[j++];
        }
        while(i<m) res[k++]=nums1[i++];
        while(j<n) res[k++]=nums2[j++];
        // 一种统一处理中位数的技巧
        int left=(len+1)/2;
        int right=(len+2)/2;
        // 从两个有序数组中查找第left大和第right大的数
        double mean=(res[left-1]+res[right-1])/2.0;
        return mean;
    }

2、二分查找

算法的时间复杂度应该为 O(log (m+n))，显然这是二分查找算法才能有的时间复杂度。显然我们已经知道如何求数组中的中位数，先写出来：

    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size();
        int n = nums2.size();
        // 想要寻找的位置
        int left=(m+n+1)/2;
        int right=(m+n+2)/2;
        // 从两个有序数组中查找第left大和第right大的数
        double mean=(findKth(nums1,nums2,0,0,left)+findKth(nums1,nums2,0,0, right))/2.0;
        return mean;
    }

现在的关键是如何在两个有序数组中找到第k大的某个数，设为findKth()。

定义该函数的含义为：

// 从nums1的[i:]和nums2[j:]的两个有序区间中查找第k大的数

int findKth(vector<int>&  nums1, vector<int>&  nums2,int i,  int j, int k)

随着在查找中不断排除来缩小问题规模，显然从两个有序区间中查找第1个数的时候就很容易得到答案：

if(k==1) return min(nums1[i], nums2[j]);// 查找第1个元素，直接返回

在缩小问题规模时，如果某个有序区间已经不存在，即i>=nums1.size()或者j>=nums2.size()时，查找中位数也会变得简单：

if(i>=nums1.size()) return nums2[j+k-1];//nums1为空数组,直接从nums2中找

if(j>=nums2.size()) return nums1[i+k-1];//nums2为空数组,直接从nums1中找

 难点就在于一般的情况怎么处理？因为我们需要在两个有序数组中找到第K个元素。

为了加快搜索的速度，我们要使用二分法，对K二分，意思是我们需要分别在nums1和nums2中查找第K/2个元素，注意这里由于两个数组的长度不定，所以有可能某个数组没有第K/2个数字，所以我们需要先检查一下，数组中到底存不存在第K/2个数字，如果存在就取出来，否则就赋值上一个整型最大值

如果某个数组没有第K/2个数字，那么我们就淘汰另一个数字的前K/2个数字即可。有没有可能两个数组都不存在第K/2个数字呢，这道题里是不可能的，因为我们的K不是任意给的，而是给的m+n的中间值，所以必定至少会有一个数组是存在第K/2个数字的。最后就是二分法的核心啦，比较这两个数组的第K/2小的数字midVal1和midVal2的大小，如果第一个数组的第K/2个数字小的话，那么说明我们要找的数字肯定不在nums1中的前K/2个数字，所以我们可以将其淘汰，将nums1的起始位置向后移动K/2个，并且此时的K也自减去K/2，调用递归。反之，我们淘汰nums2中的前K/2个数字，并将nums2的起始位置向后移动K/2个，并且此时的K也自减去K/2，调用递归即可。

// 从nums1的[i:]和nums2[j:]的两个有序区间中查找第k大的数
    int findKth(vector<int>&  nums1, vector<int>&  nums2,int i,  int j, int k){
        // 终止条件
        if(i>=nums1.size()) return nums2[j+k-1];//nums1为空数组,直接从nums2中找
        if(j>=nums2.size()) return nums1[i+k-1];//nums2为空数组,直接从nums1中找
        if(k==1) return min(nums1[i], nums2[j]);// 查找第1个元素，直接返回
        // 查找nums1中的第k/2大元素，不存在则设为无穷大
        int midVal1=(i+k/2-1<nums1.size())? nums1[i+k/2-1] : INT_MAX;
        // 查找nums2中的第k/2大元素，不存在则设为无穷大
        int midVal2=(j+k/2-1<nums2.size())? nums2[j+k/2-1] : INT_MAX;
        // 如果midVal1<midVal2，说明中位数肯定不在nums1的前k/2个数
        if(midVal1<midVal2) return findKth(nums1, nums2, i+k/2,j, k-k/2);
        // 如果midVal1>=midVal2，说明中位数肯定不在nums2的前k/2个数
        else return findKth(nums1, nums2, i,j+k/2 , k-k/2);
               
    }