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

思路

Reference：https://blog.csdn.net/chen_xinjia/article/details/69258706
这道题要求对数级别的空间复杂度，因此肯定要使用binary-search。

中位数是什么？中位数指的是，在一个数组里，有一个数，在此数左边的值均小于等于此数，在此数右边的值均大于等于此数，且左边数的数量和右边数的数量相同。

在此道题目题目里，给定的数组已经满足了有序性，所以我们需要做的是，将nums1和nums2在逻辑上看为同一个数组，我们在脑海里将其命名为nums3，找到一个数，保证在nums3里，此数的左右两侧数目相同。

我们于是使用一个“切”的说法，将nums1和nums2切开左右两边，保证：

nums1切割处的左边小于nums1切割处的右边（由于是有序数组，所以这一点无需我们担忧）
nums2切割处的左边小于nums2切割处的右边（由于是有序数组，所以这一点无需我们担忧）
nums1切割出的左边小于nums2切割处的右边（此处需要我们进行判断）
nums2切割处的左边小于nums1切割处的右边（此处需要我们进行判断）

由于nums3的数量固定，所以逻辑上的切分处，两边数目固定，为nums3.size()/2=(nums1.size()+nums2.size())/2。将两个数组切割处为cut1,cut2，不难得出cut2=nums3.size()/2-cut1。

于是我们只需要知道nums1的切割处，即可知道nums2的切割处。

问题在此转换为确认nums1切割处，而nums1切割处只可能是nums1数组开头处、nums1中间和nums2末尾，此时便可使用binary_search，对nums1切割处的合法性进行判断。

什么是nums1切割处的合法性？之前已经提过了哦。

nums1切割处的左边小于nums1切割处的右边（由于是有序数组，所以这一点无需我们担忧）
nums2切割处的左边小于nums2切割处的右边（由于是有序数组，所以这一点无需我们担忧）
nums1切割出的左边小于nums2切割处的右边（此处需要我们进行判断）
nums2切割处的左边小于nums1切割处的右边（此处需要我们进行判断）

如果这些条件都合法，那么我们就返回结果就行了。

解法

class Solution {
 public:
  double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
    int size1 = nums1.size(), size2 = nums2.size(), size = size1 + size2;

    //保证nums1大小较短，这也是缩短时间的一个好方法。
    if (size1 > size2) return findMedianSortedArrays(nums2, nums1);

    //如果nums1为空，那么答案就是nums2中间值。此处写的好像很复杂，实际上这条式子综合了nums2数目为奇数和偶数这两种状况。
    if (size1 == 0)
      return ((double)nums2[(size2 - 1) / 2] + (double)nums2[(size2 / 2)]) / 2;

    //cut1的取值范围为cutL和cutR。初始化时，cutL和cutR分别在nums1的头尾处
    int cutL = 0, cutR = size1;
    //cut1初始化为中值。根据前面分析，只需要知道cut1，便可知道cut2处
    int cut1 = size1 / 2;
    int cut2 = size - cut1;

    while (cut1 <= size1) {
      //此处取得nums1切割处和nums2切割处的两边的值
      cut1 = (cutR - cutL) / 2 + cutL;
      cut2 = size / 2 - cut1;

      double L1 = (cut1 == 0) ? INT_MIN : nums1[cut1 - 1];
      double L2 = (cut2 == 0) ? INT_MIN : nums2[cut2 - 1];
      double R1 = (cut1 == size1) ? INT_MAX : nums1[cut1];
      double R2 = (cut2 == size2) ? INT_MAX : nums2[cut2];

      //此处为合法性判断
      if (L1 > R2)
        cutR = cut1 - 1;
      else if (L2 > R1)
        cutL = cut1 + 1;
      else {
        //如果合法，则根据奇偶情况返回值
        if (size % 2 == 0) {
          L1 = ((L1 > L2) ? L1 : L2);
          R1 = ((R1 > R2) ? R2 : R1);
          return (L1 + R1) / 2;
        } else {
          R1 = (R1 < R2 ? R1 : R2);
          return R1;
        }
      }
    }
    return 0;
  }
};