【Leetcode】4.Median of Two Sorted Arrays

题目：给两个已排序的数组，长度分别为 m 和 n，找出两个数组的中位数。要求时间复杂度为 O(log(m+n))。
例如：
nums1 = [1, 3]; nums2 = [2]; 则中位数为 2
nums1 = [1,2]; nums2 = [3, 4]; 则中位数为 (2+3)/2 = 2.5

这个题目不难，问题在于他要求了算法的时间复杂度，也就是说第一反应的遍历合成新数组然后找出中位数这个最简单的方法不行，因为其时间复杂度太高。

第二个思路是参考网站讨论区这个答案，帖子很详细，记录如下。

首先，思考中位数的含义：统计学中，中位数的作用是将数集分割成两等份，其中一个数集永远比另一个大。

如果，随机将数组 A 切割，A 有 m 个数字，那么有 m+1 种切割方式。分为左右两个部分 length(left_A) = i, length(right_A) = m-i，左右可能为空。同样，将数组 B 用 j 切割，将 left_A 和 left_B 组成 left_part，同理获得 right_part。则：

length(left_part) == length(right_part)
max(left_part) <= min(right_part)
则：median = ( max(left_part) + min(right_part) )/2

那么要保证以上两个条件，则需要：

i + j == m-i + n - j (or: m-i + n-j + 1)  // 若 n >= m, 可设置 i = 0~m, j = (m + n + 1)/2 - i
B[j-1] <= A[i] and A[i-1] <= B[j]

ps.1 先假定 A[i-1], B[j-1], A[i], B[j] 总存在，之后再考虑边缘值问题
ps.2 设定 n>=m，是为了保证 在如此设定 i,j 值的情况下 j 是个非负数

因此，我们需要做的是：

在 [0, m] 区间内找到 i，满足：B[j-1] <= A[i] 和 A[i-1] <= B[j] ( j=(m+n+1)/2 -i )

然后做一个二叉树查找：

1. 设置 imin = 0, imax = m, 然后在 [imin, imax] 中开始查找
2. 设置 i = (imin + imax)/2, j = (m + n + 1)/2 - i
3. 有三种情况我们要考虑：
   a. B[j-1] <= A[i] and A[i-1] <= B[j]：意味着找到了 i，停止查找
   b. B[j-1] > A[i]：意味着 i 太小，调整搜索范围至 [i+1, imax]
   c. A[i-1] > B[j]：意味着 i 太大，调整搜索方位至 [imin, i-1]

找到 i，则中位数也可以确定了：
m+n 为奇数，则中位数为 max(A[i-1], B[j-1])
m+n 为偶数，则中位数为 (max(A[i-1], B[j-1]) + min(A[i], B[j]))/2

现在考虑边缘值问题：当 i，j 值为 0 或者 m、n 时，A[i-1], B[j-1], A[i], B[j] 可能不存在。实际上，这种情况更简单，只需要在一边寻找即可。比如，当 A[i-1] 不存在，那么我们不需要满足 A[i-1] <= B[j]。

以上为分析过程，我的 C++ 代码如下：

class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
    int m = nums1.size();
    int n = nums2.size();
    if(m > n) return findMedianSortedArrays(nums2,nums1);

    int i,j, max_left, min_right;
    int imin = 0, imax = m;
    
    while(imin <= imax){
        i = (imin + imax)/2;
        j = (m + n + 1)/2 - 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_left = nums2[j-1];
            else if(j==0) max_left = nums1[i-1];
            else max_left = max(nums1[i-1], nums2[j-1]);
            break;
        }
    }
    
    if((m+n) %2 == 1) return max_left;

    if(i==m) min_right = nums2[j];
    else if(j==n) min_right = nums1[i];
    else min_right = min(nums1[i], nums2[j]);
            
    return (max_left + min_right) / 2.0;
            
        
    
    }
};