LC4　寻找两个正序数组的中位数¶

困难通过率 44.8%python3核心代码模式二分查找样例通过牛客 AC数组二分查找分治

牛客原题　源码

讲解章节：二分

一句话

在较短的数组上二分切分点，让左半恰好凑够一半且整体不超过右半。

解题思路¶

这题考什么¶

中位数的定义只关心一件事：把两个数组合起来的 m + n 个数切成两半，左半的每个数都不超过右半的每个数，且左半的个数是定死的。这个「切」不需要真的把数组合并出来，更不需要排序。

两个数组各自有序，所以一刀切下去只有一个自由度：在 nums1 上取前 i 个进左半， nums2 上就必须取前 j 个，其中

half = (m + n + 1) // 2      左半要装的元素个数
j    = half - i

「+1」是为了让总数为奇数时左半比右半多装一个，于是中位数就是左半的最大值，奇偶两种情形能共用同一个 half，不必分两套下标算式。

一个切分点合法，要求「左半的每个数 <= 右半的每个数」。两段各自有序，段内的大小关系自动成立，只剩下交叉的两组要检查：

条件 A：nums1[i-1] <= nums2[j]
条件 B：nums2[j-1] <= nums1[i]

关键在于只用二分 A 就够了。把 A 看成关于 i 的判定函数：i 变大时 nums1[i-1] 不减、nums2[half-i] 不增，所以 A 沿 i 是 True...True False...False，这正是二分「上界」（找最后一个满足判定的位置）的形状，见二分的 44.2 节写法二。

取满足 A 的最大 i，B 自动成立。反证：设 i 是最大的满足 A 者，若 B 不成立，即 nums2[j-1] > nums1[i]，那么把 nums1[i] 与 nums2[(j-1)] 对照可知 i + 1 也满足 A（nums1[(i+1)-1] = nums1[i] < nums2[j-1] = nums2[half-(i+1)]），与 i 最大矛盾。i 已经取到 m 时 nums1[i] 是正无穷哨兵，B 直接成立； j 为 0 时 nums2[j-1] 是负无穷哨兵，同样直接成立。于是一次二分定出 i，切分点就合法了。

切定之后取答案：

max_left  = max(nums1[i-1], nums2[j-1])      左半的最大值
min_right = min(nums1[i],   nums2[j])        右半的最小值
总数为奇数 -> max_left；为偶数 -> 两者的平均。

必须在较短的数组上二分。开头把两个数组按长度摆正，二分区间就是 [0, m]，轮数是 O(log(min(m, n)))，也就是题面要的 O(log(m+n)) 级别；更重要的是这样能保证 j = half - i 永远落在 [0, n] 内： m <= n 时有 m <= half <= n，于是 j >= half - m >= 0 且 j <= half <= n。不摆正的话 j 会算出负数或超过 n，取值当场越界。

数据规模与复杂度¶

0 <= m, n <= 1000，且 1 <= m + n <= 2000，元素在 [-1e6, 1e6]。 两个数组之一可以是空的（m 与 n 的下界都是 0），只是不会同时为空。时间 O(log(min(m, n)))：二分区间长度至多 1000，至多 10 轮，每轮 O(1)。空间 O(1)：只有几个下标与哨兵变量，没有建新数组。

坑在哪¶

合并两个数组再排序是 O((m+n)log(m+n))，m + n = 2000 时不过两万次比较，跑得飞快也能通过判题，但题面把 O(log(m+n)) 写成了硬性要求，合并法不满足；归并到中间位置就停的做法是 O(m+n)，同样不满足。取舍很清楚：想过题两行就够，想满足要求才需要这套切分点二分。
边界哨兵要用正负无穷，不能用「比 1e6 大一点的常数」。题面此刻给的值域是 [-1e6, 1e6]，可硬编码常数是把正确性押在题面的值域描述上，换一道同类题（或题面值域改了）就会静默出错。float("inf") 与 float("-inf") 与具体值域无关，永远是安全的空集边界。
哨兵只在取答案时需要，二分循环里用不上：上取整的 mid 保证 1 <= i <= m，所以 nums1[i-1] 合法；而 i >= 1 又推出 j <= half - 1 <= n - 1，所以 nums2[j] 也合法。循环里再套一层哨兵判断不是错，但会掩盖这个事实。
上界二分的 mid 必须上取整，写成 (lo + hi + 1) // 2。用下取整时， hi == lo + 1 且 A 在 lo 处成立会让 mid == lo、lo = mid 原地不动，死循环。这是二分写法二的生命线，见 44.2 节。
half 里的 +1 不能省。写成 (m + n) // 2 时，总数为奇数的情形下左半会少装一个，中位数变成右半的最小值，代码的取值逻辑就得跟着改一套。
i = 0（nums1 一个都不进左半）这条路径必须靠 if i > 0 挡住，不能直接写 nums1[i-1]。Python 的负下标不是越界而是从末尾数，后果分两种，都很难查：m 为 0 时 nums1 是空表，nums1[-1] 抛 IndexError； m > 0 但 nums1 的元素都偏大时（此时二分正好定出 i = 0）， nums1[-1] 安静地取到 nums1 的最后一个元素，中位数直接算错却不报错。右半的 nums2[j-1] 同理，j = 0 时也要挡。顺带一提，m 为 0 时二分区间是 [0, 0]，循环一轮都不进，答案全部从 nums2 里取，这条路径本身不需要特判。
返回值是浮点数。meta.json 的 judge 给本题配了 eps 1e-5，按相对误差比对，所以 2 与 2.0 都算对；但除法要用 / 而不是 //，整除会把 (2 + 3) / 2 = 2.5 压成 2。

样例复核¶

nums1 = [1,3]、nums2 = [2]：较短的是 [2]，摆正后 nums1 = [2]、nums2 = [1,3]， m = 1、n = 2、half = (3 + 1) // 2 = 2。二分区间 [0, 1]：

i = 1，j = 1，nums1[0] = 2 <= nums2[1] = 3，条件 A 成立，lo = 1，收敛。

i = 1、j = 1：左半是 {2} 与 {1}，max_left = 2；总数 3 为奇数，答案 2.0，与样例一致。

nums1 = [1,2]、nums2 = [3,4]：长度相同不摆正，m = n = 2、half = 2。区间 [0, 2]：

i = 1，j = 1，nums1[0] = 1 <= nums2[1] = 4，lo = 1；
i = 2，j = 0，nums1[1] = 2 <= nums2[0] = 3，lo = 2，收敛。

i = 2、j = 0：左半是 {1,2} 与空集，max_left = 2；右半是空集与 {3,4}，min_right = 3；总数 4 为偶数，答案 (2 + 3) / 2 = 2.5，与样例一致。

参考实现¶

solutions/leetcode/LC4/sol.py
from typing import List, Optional


class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        # 摆正：始终让 nums1 是较短的那个。这既把二分轮数压到 O(log(min(m, n)))，
        # 也保证下面的 j = half - i 永远落在 [0, n] 内，取值不会越界
        if len(nums1) > len(nums2):
            nums1, nums2 = nums2, nums1
        m = len(nums1)
        n = len(nums2)
        # 左半部分要装的元素个数。+1 让总数为奇数时左半比右半多装一个，
        # 于是中位数就是左半的最大值，奇偶两种情形共用同一套下标算式
        half = (m + n + 1) // 2
        # 二分切分点 i：nums1 取前 i 个进左半，nums2 就得取前 half - i 个。
        # 判定条件取 nums1[i-1] <= nums2[half-i]，它沿 i 是 True...True False...False，
        # 要找的是最后一个 True，即二分的「上界」写法
        lo = 0
        hi = m
        while lo < hi:
            # **上取整**是上界写法的生命线：它保证 lo < i <= hi，
            # 于是 lo = i 一定让左端严格右移。下取整会在 hi == lo + 1 时原地打转
            i = (lo + hi + 1) // 2
            j = half - i
            # 这里不需要哨兵：上取整保证 i >= 1，所以 nums1[i-1] 合法；
            # i >= 1 又推出 j <= half - 1 <= n - 1，所以 nums2[j] 也合法
            if nums1[i - 1] <= nums2[j]:
                # 交叉条件成立，i 本身可能就是最大的合法切分点，必须留在区间里
                lo = i
            else:
                # nums1[i-1] 太大，切多了；比 i 更大的切法只会更糟，整段排除
                hi = i - 1
        # 收敛到最大的合法切分点，另一半的切分点随之确定
        i = lo
        j = half - i
        # 空集的边界用正负无穷，而不是「比值域大一点的常数」——后者把正确性
        # 押在题面的值域描述上，值域一变就静默出错
        max_left = float("-inf")
        # i == 0 时 nums1 一个都不进左半，必须靠 i > 0 挡住。直接写 nums1[i-1] 会变成
        # nums1[-1]：nums1 为空时抛 IndexError，非空时安静地取到最后一个元素，答案静默出错
        if i > 0:
            max_left = nums1[i - 1]
        if j > 0 and nums2[j - 1] > max_left:
            max_left = nums2[j - 1]
        # 总数为奇数时左半比右半多一个，它的最大值就是中位数
        if (m + n) % 2 == 1:
            return float(max_left)
        # 偶数时还要取右半的最小值，同样用哨兵处理「这一侧右半为空」
        min_right = float("inf")
        if i < m:
            min_right = nums1[i]
        if j < n and nums2[j] < min_right:
            min_right = nums2[j]
        # 必须用真除法：整除会把 2.5 压成 2
        return (max_left + min_right) / 2

LC4 寻找两个正序数组的中位数¶