4. Median of Two Sorted Arrays【hard】

解题思路：

这道题咋一看像二分查找，但是仔细看题，发现有两个有序数组，而且不是让我们找一个特定的数，而是要找两个数组合并后的中位数，这样一看就比较难了，也难怪归类为hard类别。这道题除了一下介绍的二分查找法，还有两个数组分别进行二分查找的方法，不过代码量相对更多(也可能是因为笔者水平不够导致代码量过大)，而且看了下面的二分查找法后，感叹于该算法作者的脑洞，所以在这里只介绍该种方法。

**暴力方法 O((m + n)*log(m + n))：**

将两个数组合并，然后进行快排，中间的数即中位数。由于题目说了复杂度不能超过O(log(m + n))，所以这个方法当然回Time Limit Excess，所以我们得探究一种更高效的解法。

二分查找法 O(log(min(m, n)))：

首先分别把两个数组分成两边，大概为下面这种形式：(A表示nums1， B表示nums2)

          left_part          |        right_part
    A[0], A[1], ..., A[i-1]  |  A[i], A[i+1], ..., A[m-1]
    B[0], B[1], ..., B[j-1]  |  B[j], B[j+1], ..., B[n-1]

因为有序数列的性质，我们知道只要我们满足以下两个条件，我们就可以找到中位数了：

条件一：len(A_left) + len(B_left) = len(A_right) + len(B_right)

条件二：max[A_left, B_left] <= min[A_right, B_right]

为了使问题简单化，我们先只考虑 m + n 为偶数的情况下，只要满足上述两个条件，我们的中位数就等于左边的最大值加上右边的最小值除以二。

为了满足条件一，我们只要令 i + j == m + n - i - j (+ 1)即可（这里加一是为了之后考虑 m + n 为奇数的情况）

而为了满足条件二，根据有序数组的性质，我们知道只需要满足 A[i - 1] <= B[j] 且 B[j - 1] <= A[i] 即可。

接下来开始我们的算法探究：

假设我们首先随机选择一个 i (这里 0 <= i < m)，所以我们根据条件一，可以求得 j = (m + n + 1) / 2 - i；

为了满足条件二，我们开始分别比较 A[i - 1] 与 B[j] 和 B[j - 1] 与 A[i]：

不难知道可能会有四种情况：

A[i - 1] <= B[j] 且 B[j - 1] <= A[i] ：这不正是我们要找的 i 吗？可以直接返回答案
A[i - 1] > B[j] 且 B[j - 1] > A[i] ：根据有序数列的性质，再利用反证法不难证明这种情况不可能存在
A[i - 1] <= B[j] 且 B[j - 1] > A[i]：为了使情况更加接近我们的答案，也就是情况1。也就是要使 B[j - 1] <= A[i]，因为现在 B[j - 1] > A[i]，所以我们要想办法缩小 B[j - 1]，扩大A[i]，所以当然是让我们的 i 增大，否则情况会越来越远离我们的正确答案。
A[i - 1] > B[j] 且 B[j - 1] <= A[i]：与情况3恰恰相反，这里我们应该缩小我们的 i。

那我们如何缩小和扩大我们的 i 呢，那就是采用二分查找的方式啦，首先将 i 置为数组A的中间下标，如果需要增大，则把其设为上半区的中间下标，反之则设为下半区的中间下标，所以这种搜索方式的时间复杂度和二分查找的时间复杂度一样，为了使时间复杂度尽量的小，我们使A成为长度更小的那个数组，如果初始A比B长，我们则交换它们的位置。

考虑边界条件：

1.如果不存在满足条件二的情况会怎么样呢？也就是 i 走到了数组A的尽头，依旧没法满足条件二，这个时候我们不难知道如果 i 走到数组A的最左端，那么它一定是在不断地经历情况4，而这时 A[0] > B[j]，那么我们不难知道这时left_part的最大值就是B[j - 1]；反之我们也可以推出 i 到了A的最右端、j 到了B的最左端或者最右端的情况。

2.m + n 为奇数。这个时候我们不难推出 left_part 的最大值就是中位数。

3.A或B为空数组，因为当数组空的时候无法对数组进行下标访问，所以我们在进行二分查找前就应该对该情况进行特殊处理，处理方式也是很简单的啦。

实现代码：

// 4. Median of Two Sorted Arrays
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
  // 使得 nums1 短于 nums2
  int m = nums1.size();
  int n = nums2.size();
  if (m > n) {
    vector<int> temp = nums1;
    nums1 = nums2;
    nums2 = temp;
    m = m + n;
    n = m - n;
    m = m - n;
  }
  // 考虑数组长度为0的边界情况
  if (m == 0) {
    if (n == 0) {
      return 0;
    } else {
      if (n % 2 == 1) {
        return nums2[n / 2];
      } else {
        return (double)(nums2[n / 2] + nums2[n / 2 - 1]) / 2;
      }
    }
  }
  int iMin = 0, iMax = m, sizeSum = (m + n + 1) / 2, i, j;
  while (iMin <= iMax) {
    i = (iMax + iMin) / 2;
    j = sizeSum - i;
    if (nums2[j - 1] > nums1[i] && i < iMax) {
      iMin = i + 1;
    } else if (nums1[i - 1] > nums2[j] && i > iMin) {
      iMax = i - 1;
    } else {
      int maxLeft, minRight;
      if (i == 0) {
        maxLeft = nums2[j - 1];
      } else if (j == 0) {
        maxLeft = nums1[i - 1];
      } else {
        maxLeft = max(nums1[i - 1], nums2[j - 1]);
      }
      if ((m + n) % 2 == 1) {
        return maxLeft;
      }
      if (i == m) {
        minRight = nums2[j];
      } else if (j == n) {
        minRight = nums1[i];
      } else {
        minRight = min(nums1[i], nums2[j]);
      }
      return (double)(maxLeft + minRight) / 2;
    }
  }
  return 0;
}

问题描述：

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Example 1:

nums1 = [1, 3]
nums2 = [2]

The median is 2.0

Example 2:

nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

4 Median of Two Sorted Arrays