LeetCode 4. 寻找两个正序数组的中位数：一道 Hard 背后的二分思想

LeetCode 第 4 题（寻找两个正序数组的中位数）常年占据「最经典 Hard」的位置：给定两个非递减排序的数组，要求在 O(log(m+n)) 时间复杂度内求出合并后数组的中位数——而题面特意标注的进阶要求，正是把「合并后取中间」这条人人会写的 O(m+n) 路封死。这道题考的从来不是代码量（正确实现只有二十来行），而是能否完成一次视角跃迁：把「取中位数」重构为「找第 k 小」，再把「找第 k 小」重构为「每次安全地丢弃一批不可能的候选」。它也是二分查找家族里最考验边界的题目：从 2018 年到现在，各大面试题库里它的出现频率从未掉出前列，原因无他——它把「会二分」和「懂二分」用一道题分开。本文沿这条线把两种主流解法讲透，代码全部本地验证（含两万组随机对拍）。

一、题目与约束

题面：给定两个大小分别为 m 和 n 的非递减数组 nums1 与 nums2，返回合并后数组的中位数；奇数长度返回中间元素，偶数长度返回两个中间元素的平均。数值范围 [-10⁶, 10⁶]，题解页明确要求时间复杂度 O(log(m+n))。两个细节先钉死：允许空数组（一个数组长度为 0 是合法输入，处理不当会数组越界——后文的对拍会真的踩到它的变体）；中位数位置对偶数长度是「两个中间值的平均」，整数除法与浮点转换都在这里埋坑。还有一条隐含约定值得说破：两个数组不同时为空（否则中位数无定义），测试与实现都按这条约定设计。

二、解法一：找第 k 小——把中位数变成两问

第一个视角转换：中位数可以统一写成「找第 k 小」。合并后总长 total = m + n：奇数时答案是第 total // 2 + 1 小（1-indexed）；偶数时是第 total // 2 小与第 total // 2 + 1 小的平均。惯用写法是同时求第 (m+n+1)//2 与第 (m+n+2)//2 小再平均——奇数时两个位置重合，恰好自动退化。

而「在两个有序数组里找第 k 小」有个优雅的递归结构：每次比较两个数组「候选区间内第 p 个」元素（p = k//2），谁小，谁连同它前面的元素就绝不可能是第 k 小。原因一句话就能证明：如果 nums1[i+p-1] 较小，它在合并序里至多排在第 i+p-1 + j+p 位之前（前面最多有 nums1 的 p-1 个和 nums2 的 j+p 个），即至多是第 k-1 小——所以它和它前面的 p 个元素可以整体安全丢弃，k 减去 p，递归继续。每轮丢弃一半的 k，基础情形是某数组耗尽（直接在另一数组取第 k 个）或 k == 1（返回两数组当前头部较小者），总复杂度 O(log(m+n))。

用最小的例子把流程走一遍，比抽象论证更有感觉。设 nums1 = [1, 3]、nums2 = [2, 4]，总长 4，中位数是第 2 小与第 3 小的平均。找第 2 小（k=2）：p=1，比较 nums1[0]=1 与 nums2[0]=2，1 较小——丢弃它（k 减 1），进入 nums1[1:] 与 nums2 找第 1 小；k==1，返回 min(3, 2)=2。找第 3 小（k=3）：p=1，比较 1 与 2，丢弃 1；再找第 2 小（k=2）：p=1，比较 3 与 2，2 较小丢弃；找第 1 小，返回 min(3, 4)=3。答案 (2+3)/2 = 2.5，与合并数组 [1,2,3,4] 的中位数一致。三次比较走完全程——这就是「每轮扔一半」在真实输入上的样子。

class Solution:
    def findMedianSortedArrays(self, nums1, nums2):
        total = len(nums1) + len(nums2)
        if total == 0: return 0.0   # 防御：题面保证不同时为空，这里对齐参考实现

        def kth(i, j, k):
            # 在 nums1[i:] 与 nums2[j:] 中找第 k 小（k 从 1 计）
            if i >= len(nums1): return nums2[j + k - 1]
            if j >= len(nums2): return nums1[i + k - 1]
            if k == 1: return min(nums1[i], nums2[j])
            p = k // 2
            a = nums1[min(i + p - 1, len(nums1) - 1)]
            b = nums2[min(j + p - 1, len(nums2) - 1)]
            if a <= b:
                step = min(p, len(nums1) - i)   # 实际丢弃个数
                return kth(i + step, j, k - step)
            else:
                step = min(p, len(nums2) - j)
                return kth(i, j + step, k - step)

        return (kth(0, 0, (total + 1) // 2) + kth(0, 0, (total + 2) // 2)) / 2

四个易错点都在这段代码里可见：k == 1 的基础情形绝不能省（否则 k//2 得 0，死循环）；比较用的哨兵下标要 min(i+p-1, len-1) 防越界（某数组剩余长度不足 p 时，丢弃个数 step 也要相应截断）；丢弃后 k 必须同步减去实际丢弃的 step 而不是 p；两个中位位置取平均前要保证是浮点除法。这四条没有一条是算法本身的难点，全是「实现与正确性论证之间的缝隙」——随机对拍之所以必要，就是因为它们只在特定输入组合下显形。

三、解法二：切分线——面试官更爱的那一版

另一个视角更美：中位数本质是一条把合并后的数组等分成两半的切分线。在两个数组上各选一个切分位置 i 和 j（i + j = (m+n+1)//2），把 nums1 分成左右两半、nums2 分成左右两半，只要满足「左半的所有元素 ≤ 右半的所有元素」，中位数就直接由切分线两侧的边界值算出：奇数总长取左半最大值，偶数总长取「左半最大 + 右半最小」的平均。

这个条件怎么满足？关键观察：在较短数组上二分切分位置即可——i 定下后 j 由总数关系唯一确定（j = 半长 - i），而「左半 ≤ 右半」是否成立只取决于两个不等式：nums1[i-1] <= nums2[j] 且 nums2[j-1] <= nums1[i]。违反前者就把 i 右移，违反后者左移——标准二分。为什么必须在较短数组上二分？因为 j 是被 i 唯一决定的，若在长数组上取 i，算出的 j 可能为负——短数组保证了 j 的取值范围合法。边界处理是这个解法的主要工作量：切分线顶到数组两端时（i 为 0 或 m），切分线一侧没有元素，比较要用 ±∞ 哨兵补位——左半最大值的哨兵取 −∞（不存在时不约束右侧），右半最小值的哨兵取 +∞。它比第 k 小解法少一层递归、常数更小，也是大多数面试官期待听到的那版；代价是边界处理更密集，手写时翻车率更高。两版思想同源：都是在「单调的候选空间」上二分——第 k 小版二分的是 k，切分线版二分的是切分位置。

四、本地验证：边界用例 + 两万组随机对拍

设计题和 Hard 题一样，眼见为实。按官方约束写三层测试：手工边界（两数组分别为空、一长一短、完全交错、全部相同元素）；小规模穷举；以及最狠的一层——随机对拍：与「合并后排序取中位数」的朴素 O((m+n)log(m+n)) 参考实现，在固定随机种子下对跑 20000 组随机数组（长度 0–50、值域 [-10⁶, 10⁶]，刻意混入空数组与重复元素，按题面隐含保证跳过两数组同时为空的组合），逐步断言结果一致。发布前已本地运行：

边界断言通过；20000 组对拍全部一致

值得一提的是，对拍第一轮就抓到一个真 bug：最初的实现没处理两数组同时为空的退化输入，kth 直接数组越界——手工边界用例全过也挡不住随机数据撞进未定义区域。加了一行 total == 0 的防御分支后全部通过。对拍的价值在这道题里特别突出：二分解法的边界组合（k 跨数组边界、切分线顶到数组两端）多到手工枚举不全，随机数据会替你踩到「没想到的路径」。对拍通过后再对照复杂度：O(log(m+n)) 在 m=n=1000 量级时只是约十几次比较循环——这就是题目坚持要二分的实际意义。还要补一句复杂度的推导：第 k 小解法每轮 k 至少减半，所以递归深度是 log₂(k) ≤ log₂(m+n)——对 m+n=2000 的上限，深度不超过 11 层，每层只有常数次比较与一次范围截断，总比较次数是「十几次」而不是「几千次」；这也是为什么它在超长数组（如流式合并的日志段）上仍然轻盈。面试里若被追问「能不能更快」，答案是不能证明地更快：在两个无其他结构的有序数组上找中位数，比较模型下 Ω(log(m+n)) 是下界——这道题问的恰好是「踩到信息论地板」。回头再看整道题的知识结构，「合并取中间」是算法，O(log) 的两个解法是算法思想的分野，而对拍验证是工程——一道题把三层都踩了一遍，这正是它值得被反复拿来教的原因。

五、为什么它是 Hard 里的必修课

把这道题放进行业语境里看，它考的三个能力都是真需求。重构问题的能力：从「中位数」跳到「第 k 小」再到「安全丢弃」，每一步都是把模糊需求翻译成可计算结构——这正是工程师日常把业务问题变成算法的那一跃。单调性嗅觉：两种解法都依赖「丢弃决策不破坏剩余答案」的单调结构，识别它、证明它（那句 2p-1 ≤ k-1 的简短论证）是二分家族的通用心法，从旋转数组到各类「在答案空间上二分」的题目都在用。边界工程学：空数组、哨兵、截断丢弃、整数除法——Hard 题的正确率差距不在思路，全在这些缝里。

如果要在面试里讲这道题，一个可靠的叙述脚本值得预演：先花三十秒给朴素解法（合并取中间，O(m+n)，承认它不是题目要的答案）——这展示了你了解基线；再给「找第 k 小」的核心洞察（第 k 小之前最多有 k-1 个元素，所以较小一方的 p 个元素可安全丢弃），配一句 2p-1 ≤ k-1 的正确性说明；如果面试官还有兴趣，再抛出切分线视角（等分两半 + 左右有序，在短数组上二分切分点）。三层递进，每一层都比上一层更接近这道题被设为 Hard 的原因。延伸的变体也顺手记两个：把「中位数」换成「第 k 小」本身是同一套代码的简化版；把「两个有序数组」换成「k 个有序数组」则要么逐次两两归并（O(N log k)），要么用堆维护 k 路指针——同一个问题在参数变化下长出不同的最优结构，这正是算法设计最迷人的地方。能把这道题的两种解法都写对并说清取舍，「二分查找」这个知识点才算真正毕业。

参考资料

• LeetCode 4. Median of Two Sorted Arrays——题目原文与约束
• 4. Median of Two Sorted Arrays - Explanation（AlgoMonster）——第 k 小解法的正确性论证与常见陷阱
• Median of Two Sorted Arrays（NeetCode）——切分线解法的图解视角