4. Median of Two Sorted Arrays

给定两个排好序的数组：nums1和nums2，它们的大小分别是m和n，找到这两个数组的中位数，算法的复杂度应该为:
你可以假设它们都是非空的数组。

• Example 1:

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

它们的中位数是 2.0

• Example 2：

nums1 = [1, 2]
nums2 = [3, 4]
中位数是2.5

思路

https://leetcode.com/problems/median-of-two-sorted-arrays/discuss/2481/Share-my-O(log(min(mn))-solution-with-explanation
首先，中位数指的是，将数组小于该数的数放在一边，大于该数的数放在另一边，最终两边数的个数相同。那么对于两个数组，我们需要的是分别进行划分，使得划分后可以找到对应中位数。如下图所示：

划分
如果我们能够满足：
条件
就能够平均地划分，中位数就是左边最大值和右边最小值的平均值。

因此我们可以满足下面条件，来达到目的：

image.png

也就是我们从0到m，找到满足条件(2)的i即可。只是需要，因为i是从0到m，如果m大于n的话，j就有可能小于0，例如i取m的时候。

由于是排序好的数组，我们可以使用二分法查找。

1. 首先i取数组A的中间，j根据公式得到
2. 从上面得到的i和j，使得两边的数组长度相等，这时如果：
   (1). B[j-1] <= A[i] and A[i-1]<=b[j]，那么满足条件
   (2). B[j-1] > A[i]，这时A[i]太小了，需要增大i，使得A[i]增大，因为i增大，j减少，b[j-1]减少，根据二分法，i取i左边部分的中间位置
   (3). A[i-1] > B[j]，这时A[i]太大了，需要减少i，根据二分法，i取i右边部分的中间位置

边界条件：
当i=0, i=m, j=0, j=n的时候，在寻找i的过程中会出错，因为i-1,j-1不存在。

#include <iostream>
#include <vector>
#include <stdlib.h>
#include <algorithm>

using namespace std;

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        if(nums1.size() > nums2.size()) {
          nums1.swap(nums2);
        }
        int m = nums1.size();
        int n = nums2.size();
        int imin = 0;
        int imax = m;
        int ihalf = (m + n + 1) / 2;
        double max_of_left, min_of_right;

        while(imin <= imax) {
          int i = (imin + imax) / 2;
          int j = ihalf - i;

          if(i < m && nums2[j-1] > nums1[i])
            imin = i + 1;
          else if(i > 0 && nums1[i-1] > nums2[j])
            imax = i - 1;
          else {
            if(i == 0)
              max_of_left = nums2[j-1];
            else if(j ==0)
              max_of_left = nums1[i-1];
            else
              max_of_left  = max(nums1[i-1], nums2[j-1]);

            if ((m + n) % 2 == 1)
              return max_of_left;
            
            if (i == m)
              min_of_right = nums2[j];
            else if(j == n)
              min_of_right = nums1[i];
            else
              min_of_right = min(nums1[i], nums2[j]);
            
            return (max_of_left + min_of_right) / 2.0;
          }
        }
    }
};


int main() {
  vector<int> nums1 = {1, 3};
  vector<int> nums2 = {2};

  Solution solver;

  cout << solver.findMedianSortedArrays(nums1, nums2) << endl;

  vector<int> nums3 = {1, 2};
  vector<int> nums4 = {3, 4};
  cout << solver.findMedianSortedArrays(nums3, nums4) << endl;

  getchar();
}