用 PHP 在 力扣 刷算法 [寻找两个正序数组的中位数]{有空就更}

题目：题目：

给定两个大小为 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

解析：

1，看到这个题的瞬间，先不考虑题目中的时间和空间的复杂度，我用PHP的 array_merge()一下这两个数组，然后在sort() 一下，在 count() 一下，计算出中位数的下标，就得到了。当然，这肯定不符合题意的。又回到题目，我要求时间和空间复查度都要要小于log级别，看到这三个单词，我想到了 二分天下 中，这就是标准的时间空间的级别，那么，现在的问题是怎么二分？

首先：1，两个有序数组找中位数，必然中位数在其中一个有序数组中，并且在这个数组中存在这样的关系：数组中位数的左边的所有值肯定都小于右边的所有值。

其次：2，既然这个中位数是这两个有序数组的中位数，那如果合并两个数组后，比中位数小的或等于元素个数 加 比中位数大的元素个数必然等于两个数组的总数，反过来说，不合并也是存在这个等式的

再其次：3，根据第一个分析，不管两个有序数组怎么样，比中位数小的在左边，其中一个数组的比中位数小的所有元素中的最大元素 必定比另一个有序数组比中位数大的元素小，反过来也必须成立。

最后：4，我们对其中一个数组进行二分，那必然满足 2 的规则。

注意：计算中位数时，要判断两个数组的总长度，奇数是刚好中间的元素，偶数是中间两个元素的和处以2

## 分析那么多，不如看代码：

function findMedianSortedArrays($nums1, $nums2) {
        // 统计两个数组长度
        $len1 = count($nums1);
        $len2 = count($nums2);
        // 既然二分任何一个有序数组都可以，那么就选 个数小的那个进行二分, 如果传参的第一个数组大于第二个，递归一下
        if ($len1 > $len2) {
            $this->findMedianSortedArrays($nums2, $nums1);
        }
        // 再判断 $nums1 数组长度是否为 0 ，如果是零，则就是查找 $nums2 的中位数，那么就简单了三
        if ($len1 == 0) {
            // 一个有序数组 不管是奇数还是偶数，这个写法都能准确找到中位数，这个就不解释了，可以自己试试
            return ($nums2[floor($len2 / 2)] + $nums2[floor(($len2 - 1) / 2)]) / 2;
        }

        // 开始分割查找:

        // 统计一下两个数组的总长度
        $len = $len1 + $len2;

        //  对 $nums1 进行切得 下标
        $slice1 = 0;
        // 根据解析 中第二条能推导出 $nums2 得切点，但是还是要预存一下
        $slice2 = 0;
        // $nums1 的切割区间 左 和 右 
        $sliceL = 0;
        $sliceR = $len1;
        // 接下来就是在循环找找出 中位数了
        // 只要切点 不大于 长度，那么就是成立的
        while ($slice1 <= $len1) {
            // 刚进来时 先对 小的数组进行二分   ($sliceL + $sliceR)/2 和 ($sliceR - $sliceL) / 2 + $sliceL 在数学上是一样的，但是第二种可以防止内存溢出 
            $slice1  = floor($sliceR - $sliceL) / 2 + $sliceL;
            // 得到小数组的切点，那么大数组的二分切点也知道了，因为满足上面分析的第二条
            // 简单证明一下，第一个切点等式：2*$slice1 = $sliceR - $sliceL 
            // $len = $len1 + $len2 
            // 根据二分 $len2 = 2 * $slice2
            // 替换一下上面的等式 $len = 2 * $slice1 + 2 * $slice2
            // 得到下面的等式
            $slice2 = floor($len/2) - $slice1;
            // 计算 $nums1 被分过后小的半段的最大元素，比如数组 [1, 3, 4, 6, 8, 13] 中分后为 [[1, 3, 4] 和   [6, 8, 13] 
            // 根据不断的移动切点 有可能切点在 开始位置 ，当为开始位置时，要找一个肯定小的标记，这里用 PHP 的系统常量，否则就是切点的前一个
            $l1 = ($slice1 == 0) ? PHP_INT_MIN :$nums1[$slice1 - 1];
            $l2 = ($slice2 == 0) ? PHP_INT_MIN :$nums2[$slice2 - 1];
             // 同理，计算数组大的半段的最小元素 也存在一个当切点是数组长度时 
            $r1 = ($slice1 == $len1) ? PHP_INT_MAX : $nums1[$slice1];
            $r2 = ($slice2 == $len2) ? PHP_INT_MAX : $nums2[$slice2];
            // 根据解析 第三条 其中一个数组的比中位数小的所有元素中的最大元素 必定比另一个有序数组比中位数大的元素小 
            if ($l1 > $r2) {
                // 如果大了 则不是中位数 要向左移动切点，找前一个值，本体的二分就体现在这里，大了，则后面的全部值都大了，直接不进入计算了
                $cutR = $slice1 - 1;
            // 同理 $nums2 切割后 所有小的元素中的最大值也 必须小于 $nums1 切割后 所有大元素的最小值。
            } elseif ($l2 > $r1) {
                // 直接抛弃切点的前半段，在二分
                $cutL = $slice1 + 1;
            // 当上面的 两个都满足，则找到了本题的中位数了，
            } else {
                // 偶数时，中位数时 小的所有元素的最大值和大的所有元素的最小值相加除2
                if ($len % 2 ==0) {
                    $l1 = $l1 > $l2 ? $l1 : $l2;
                    $r1 = $r1 < $r2 ? $r1 : $r2;
                    return ($l1 + $r1) / 2;
                }
                // 奇数时，所有大元素的最小值
                return min($r1, $r2);
            }
        }

本题确实有难，需要时间推理和证明…

本作品采用《CC 协议》，转载必须注明作者和本文链接