〔两行哥算法系列〕两个排序数组的中位数（二）

来看看这道算法题（摘自腾讯2018秋招精选）：
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 min(m,n)).
You may assume nums1 and nums2 cannot be both empty.

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

翻译成中文：
给定两个大小为 m 和 n 的有序数组 nums1 和 nums2 。
请找出这两个有序数组的中位数。要求算法的时间复杂度为 O(log min(m,n)) 。
你可以假设 nums1 和 nums2 不同时为空。

示例 1:

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

示例 2:

nums1 = [1, 2]
nums2 = [3, 4]
中位数是 (2 + 3)/2 = 2.5

首先，我们看到题目的要求：算法的时间复杂度为 O(log min(m,n)) ，说明这道题有一个隐性要求：使用二分法查找。还需要留意，题目中给出的两个数组为Sorted，即有序数组。OK，我们开始分析题目。

首先，我们需要明白中位数的数学定义：

定义1：中位数，又称中点数，中值。中数是按顺序排列的一组数据中居于中间位置的数，即在这组数据中，有一半的数据比它大，有一半的数据比它小。

定义2：如果我们把一组有序数据分为两个长度一样的集合（或者两个集合长度差为1），其中一个集合的任意值都小于另外一个集合中的最小值，此时分界点值即为中位值。

其次，根据数学定义对目标数组进行分割并推导解题条件：

题目中已经给出长度分别为m和n的有序数组，用arrayA与arrayB表示这两个数组，并假定m<=n（如果m>n，就将两个数组交换，然后再进行分析）
现在我们将arrayA在i索引处进行分割，得到两个子数组：

subArrayA1 = [ a0 , a1 , a2 ...... , a(i - 1) ]，共i个元素
subArrayA2 = [ a(i) , a(i + 1) , a(i + 2) ...... , a(m - 1) ]，共m - i个元素

此时，i 的取值范围为[0 , m]，当i = 0时，subArrayA1为空数组，当i = m时，subArrayA2为空数组。

由于数组长度为m，可以知道共有m + 1种分割方法。

同理，我们对arrayB进行分割，得到两个子数组：

subArrayB1 = [ b0 , b1 , b2 ...... , b(j - 1) ]，共j个元素
subArrayB2 = [ b(j) , b(j + 1) , b(j + 2) ...... , b(n - 1) ]，共n - j个元素

此时，j 的取值范围为[0 , n]，当i = 0时，subArrayB1为空数组，当i = n时，subArrayB2为空数组。

由于数组长度为n，可以知道共有n + 1种分割方法。

这时候我们将subArrayA1和subArrayB1放入同一个集合leftArray，将subArrayA2和subArrayB2放入另外一个集合rightArray，如果满足如下条件：

条件1：leftArray.length == rightArray.length （或 leftArray.length == rightArray.length +- 1）

条件2：max(leftArray) <= min(rightArray)

那么，我们已经将arrayA和arrayB中所有的元素划分为相同长度的两个部分，且其中一部分中的元素总是大于另一部分中的元素。根据上文定义1和定义2，我们可以发现此时的leftArray和rightArray即满足中位值分割，我们就可以求出相应的中位值。

接着，根据条件推导变量 i 与 j 之间的数学关系：

我们对条件1和条件2进行分析，可以求出此时i , j , m , n之间的数量关系，如下：

由条件1可得：i + j = ( m - i ) + ( n - j ) （或 i + j = ( m - i ) + ( n - j ) +- 1），这里 i 的取值范围为[0 , m]，并且上文也已经声明m <= n，此时 j = (m + n) / 2 - i
由条件2可得：a(i - 1) <= b(j)并且b(j - 1) <= a(i)

注意：
1.本文开头声明m <= n，如果不满足，则交换两个数组。为什么呢？因为 i 的取值范围为[0 , m]， j = (m + n) / 2 - i，当 i 取最大值m时，如果 m > n ，就会导致 j 的值小于0，这是错误的。
2.这里忽略了临界点：i = 0 或 j = 0 或 i = m 或 j = n，始终假定a(i - 1) 、a(i)、b(j - 1)、b(j)存在。关于临界点将在后文进行处理。

最后，我们根据推导出的数学关系，总结算法要求：

在[ 0 , m ]中，找到值 i ，使得：

a(i - 1) <= b(j) 并且 b(j - 1) <= a(i) ，这里的 j = (m + n) / 2 - i

隐性要求：使用二分法查找 i

可能有些读者对二分法查找不太熟悉，这里两行哥先带大家梳理一下查找逻辑：
设iMin=0，iMax=m，然后在[iMin,iMax]中进行搜索。
令 i =iMin + (iMin + iMax) / 2 ， j = (m + n) / 2 - i，此时已经满足：
leftArray.length == rightArray.length （或 leftArray.length == rightArray.length +- 1）。
接下来只会遇到三种情况：

1. a(i - 1) <= b(j) 并且 b(j - 1) <= a(i)：

这意味着我们找到了目标 i ，可以停止搜索。

2.b(j - 1) > a(i)：

这意味着 a(i)太小，我们必须调整 i 以使 b(j - 1) <= a(i)。
我们可以增大 i 吗？
是的，因为当 i 被增大的时候，j 就会被减小。
因此 b(j - 1) 会减小，而 a(i) 会增大，那么 b(j - 1) <= a(i) 就可能被满足。
我们可以减小 i 吗？
不行，因为当 i 被减小的时候，j 就会被增大。
因此 b(j - 1) 会增大，而 a(i) 会减小，那么 b(j - 1) <= a(i) 就不可能满足。
所以我们必须增大 i 。也就是说，我们必须将搜索范围调整为 [i + 1 , iMax]，并重新开始搜索。

3.a(i - 1) > b(j)：

这意味着 a(i - 1) 太大，我们必须减小 i 以使 a(i - 1) <= b(j) 。 也就是说，我们必须将搜索范围调整为 [iMin , i−1]，并重新开始搜索。

当找到目标对象 i 时，则可以分析出中位数：

如果m + n为偶数，则中位数为(Max(leftArray) + Min(rightArray)) / 2

如果m + n为奇数，此时leftArray.length与rightArray.length长度差为1，有如下两种情况：

1. leftArray.length > rightArray.length，中位数为Max(leftArray)
2. leftArray.length < rightArray.length，中位数为Min(rightArray)

最后让我们来分析一下遗留问题，当i = 0 或 j = 0 或 i = m 或 j = n 时，a(i - 1) 、a(i)、b(j - 1)、b(j)则可能不存在。通常情况下，我们需要分析a(i - 1) <= b(j) 并且 b(j - 1) <= a(i) 这两个条件是否成立，如果有一个条件中某个元素不存在，则只需要分析另外一个条件是否成立。比如，当i = 0 时， a(i - 1)不存在，此时只需要分析b(j - 1) <= a(i)是否成立。请读者仔细想想，是不是这样？

最后附上代码实现：

    public int[] A = {2, 7, 11, 15};
    public int[] B = {3, 8, 12, 16, 18};


    public double getResult() {
        int m = A.length;
        int n = B.length;
        if (m > n) { //确保m<=n，否则就将A和B交换
            int[] temp = A;//交换A和B
            A = B;
            B = temp;
            int tmp = m;//交换m和n
            m = n;
            n = tmp;
        }
        int iMin = 0, iMax = m;
        while (iMin <= iMax) {//在iMin与iMax之间进行二分查找
            int i = iMin + (iMax - iMin) / 2;//取iMin与iMax的中间值作为i的值
            int j = (m + n) / 2 - i;//根据i的值算出j的值
            if (B[j - 1] > A[i]) {//j过大，i过小，将i的最小值重新赋值
                iMin = i + 1;
            } else if (A[i - 1] > B[j]) {//i过大，j过小，将i的最大值重新赋值
                iMax = i - 1;
            } else {//找到合适的i
                int maxLeft;//寻找leftArray的最大值
                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]);
                }

                int minRight;//寻找rightArray的最小值
                if (i == m) {
                    minRight = B[j];
                } else if (j == n) {
                    minRight = A[i];
                } else {
                    minRight = Math.min(B[j], A[i]);
                }

                if ((i + j) < (m + n - i - j)) {//当leftArray长度小于rightArray
                    return minRight;
                } else if ((i + j) > (m + n - i - j)) {//当leftArray长度大于rightArray
                    return maxLeft;
                } else {//当leftArray和rightArray长度一致
                    return (maxLeft + minRight) / 2.0;
                }
            }
        }
        return 0.0;
    }

我们对算法复杂度进行分析：
因为采用了二分法查找，在最坏的情况下，算法的时间复杂度为O(log min(m , n))，底数为2。
我们在算法中额外定义了9个临时变量，分别为int m、int n、int temp、int iMin、int iMax、int i、int j、int maxLeft、int minRight，因此算法的空间复杂度为O(1)。

这篇文章就讲到这里，核心思想就两个，一个是理解中位数的含义，另外一个就是要通过算法复杂度为O(log min(m,n))发现题目隐含条件：使用二分法查找，不可以枚举查找。