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

我的解法：

标准解法：

class Solution {
    public double findMedianSortedArrays(int[] A, int[] B) {
        int m = A.length;
        int n = B.length;
        if (m > n) { // to ensure m<=n
            int[] temp = A; A = B; B = temp;
            int tmp = m; m = n; n = tmp;
        }
        int iMin = 0, iMax = m, halfLen = (m + n + 1) / 2;
        while (iMin <= iMax) {
            int i = (iMin + iMax) / 2;
            int j = halfLen - i;
            if (i < iMax && B[j-1] > A[i]){
                iMin = i + 1; // i is too small
            }
            else if (i > iMin && A[i-1] > B[j]) {
                iMax = i - 1; // i is too big
            }
            else { // i is perfect
                int maxLeft = 0;
                if (i == 0) { maxLeft = B[j-1]; }
                else if (j == 0) { maxLeft = A[i-1]; }
                else { maxLeft = Math.max(A[i-1], B[j-1]); }
                if ( (m + n) % 2 == 1 ) { return maxLeft; }

                int minRight = 0;
                if (i == m) { minRight = B[j]; }
                else if (j == n) { minRight = A[i]; }
                else { minRight = Math.min(B[j], A[i]); }

                return (maxLeft +    minRight) / 2.0;
            }
        }
        return 0.0;
        }
}

解析：

求解两个数组的中位数，由于该题要求时间复杂度为lg(m+n)，因此可知，默认要用递归法解决该问题，由于中位数的特殊性，我们考虑求出数组中的最中间的两个数，由于两数组都是有序的，我们可以将两数组分为如下两部分

左	右
A[0],···,A[i-1]	A[i],···,A[m-1]
B[0],···,B[j-1]	A[j],···,A[n-1]

我们将表左边的数看成一部分，将表右边的数看成一部分，由于我们求解的是中位数，因此，表左边的部分和表右边的部分，数字个数应该相同，即

i + j = m -i + n - j

这里就对 i 与 j产生了关系，即

j = ((m + n) - 2 * i) / 2

但是这种情况下，如果m + n为奇数，则，j 和 i 就会出现一个大一个小的情况，毕竟整数除法是向下取整，因此，我们选择让j遵循如下公式：

j = ((m + n + 1) - 2 * i) / 2

如果 m + n为奇数，例如m + n为 5,那么产生的i = j = 3 ，因为 m + n + 1 的缘故，导致了这种情况，那么这种情况对于解题是否有坏处呢？答案是没有，相反这种情况下，中位数正好是左边最大的和右边最小的，并且这两个数相等，当然也可以写成：

(maxLeft + minRight) / 2

如果 m + n为偶数呢，例如 m + n 为 6,那么产生的 i = j = 3，因为 m + n + 1 的缘故，j = 7 / 2 = 3 并不影响计算，而此时，中位数为左边最大的和右边最小的的和除以2，即

(maxLeft + minRight) / 2

到这里，我们大致思路已经整理清楚，问题变成了求解一个i 的问题，而 i 的取值为多少？[0,m]。这里会产生疑问？为何 i 的值会为 0 或者 m，答案是当A数组为空数组时，i则为 0, 因此，此时，左边的最大值就是B[j - 1], 当j = 0 时同理。那么何时i为m呢?即，A数组整体小于B数组时，此时右边的最小值则为B[j]，i会出现上述两种情况，j也同理，此处不再赘述。

对于两数组的数量关系我们已经搞懂，那么还有一个大小关系，由于是中位数，需要保证

A[i - 1] < B[j]
A[i] > B[j - 1]

此处相对比较容易理解。

那么问题来了，我们如何查找满足上述两个条件，即

（1）左边数组与右边数组长度相等
（2）A[i - 1] < B[j]，A[i] > B[j - 1]

的 i 值呢。

采用循环的方式寻找固然是一种办法，但是由于题目的要求，自然是采用二分的想法，否则无法达到规定的时间复杂度。

由于i的取值范围已经确定，我们就从[0,m]两侧同时寻找，但在寻找过程中，会出现如下情况：

A[i - 1] < B[j]，A[i] > B[j - 1]，这表明，已经找到正确答案，可以进行中位数求解。
A[i - 1] > B[j],这意味着，当前的 i 太大了,由于我们使用的是递归的思想，因此，缩小查找范围从[imin,i-1]的范围开始找，与此同时要保证i > imin，因为i值明显大了，所以不用考虑i < imax。
A[i] < B[j - 1],这意味着，当前的 i 太小了,由于我们使用的是递归的思想，因此，缩小查找范围从[i+1,imax]的范围开始找，与此同时要保证i < imax，因为i值明显小了，所以不用考虑i > imin。

这样递归算法也设计完全了，寻找i值也就简单了。