刷算法题的人，十有八九会遇到这道“寻找两个正序数组的中位数”——第4题，它在算法题库里的位置非常靠前，几乎是二分查找的必修课。题面看起来简单到不行：两个正序数组，求合并后的中位数，可复杂度偏偏要求 O(log(m+n))，直接把“先合并再排序”的念头摁死。这道题适合两类人：一类是准备面试、想把二分边界练扎实的人；另一类是卡在“为什么不能直接合并”“为什么排除一半就是安全的”这些坎上的初学者。看完这篇文章，我不光给你能跑的代码，更要把里面的门道拆开讲透。

1. 题面理解与考点定位

1.1 中位数这道题的隐藏前提

先停下来读题。题目给的是两个“正序”数组，这个前缀不是随手加的。中位数的定义大家都很熟：合并后的总长度是奇数，取中间那个数；总长度是偶数，取中间两个数的平均值。但真正决定这题难度的是“有序”这两个字。如果两个数组都是乱序的，那唯一可靠的办法就是合并后重新排序，绕不开 O(m+n)。既然它们各自有序，就说明有现成的排列信息可以复用，我们可以通过局部比较，不断收缩答案范围，而不必真的把两个数组合成一个新数组。

新手特别容易在这块掉坑：题目说的是“合并后的中位数”，于是第一反应就是先合并。合并本身就要遍历完两个数组，哪怕用双指针归并，也是 O(m+n)，题目不允许。换个角度想，中位数不一定非要“合并之后”才能确定，它完全可以被描述成一个排名问题——在两组有序数据的合集里，找到第 k 小的元素。当总长是奇数时，中位数就是第 total//2+1 小的数；偶数时，就是第 total//2 和第 total//2+1 小的两个数的平均。一旦做了这个转化，题目就从“找一个特定值”变成了“找第 k 小”，后面的思路全都可以围绕排名展开。

1.2 复杂度要求传递的信号

O(log(m+n)) 这个复杂度，等于把答案提前写在题面里了。想达到 log 级别，唯一的正道就是每轮操作能排除掉大约一半的候选元素——这就是二分查找的思路。很多人的误区是以为这题是“在两个数组里二分”，其实不是，这里二分的是“候选元素集合的大小”。每次通过比较，把确定不可能是答案的一段直接扔掉，让剩余候选数量按指数级下降，直到剩下最后一个。

这里有个很直观的类比：你想知道全班成绩排名第 10 的人是谁，不需要真的把所有成绩列出来排一遍，而是可以分组做擂台比较。每次找两组候选人里比较靠前的部分，谁弱谁出局，一轮就能淘汰掉一大批人，几轮下来就能锁定目标。这个直觉，就是整道题的核心。从复杂度倒推出算法方向，也是面试官最想看到的能力——不是背模板，而是能根据约束条件反推设计思路。

2. 核心思路：从“合并找中位数”到“找第k小”

2.1 中位数与第k小的关系

解决这道题最容易理解的高效方法，是“递归二分排除法”。思路一句话就能说清：我们要找合并后的第 k 小数，每次在两个数组的当前范围内，各拿出前 k//2 个元素来比较，谁那边的最后一个元素更小，说明那一段里不可能存在第 k 小的数，可以整块丢弃。反复做下去，直到 k 变成 1，答案就是当前两个数组头部的较小值。

难点从来不是这句话，而是“为什么可以这样丢”。这部分我会掰开讲。假设数组 A 的前 p 个元素，整体上都不大于数组 B 的前 q 个元素（p+q = k），那么 A 的这 p 个元素一定不可能是第 k 小。道理很简单：因为光 B 里就已经有 q 个元素排在它们前面了，再加上 A 自己前面的 p-1 个元素，它们最乐观也就排到第 p+q-1 名，也就是第 k-1 名，永远摸不到第 k 名的位置。所以丢掉它们，不会弄丢真正的答案。

2.2 二分排除法的安全删除原则

“安全删除”这四个字，是整道题的基石，值得反复咀嚼。具体到每次操作：我们比较 A 和 B 的第 k//2 个元素，谁更小，就把谁所在数组的前 k//2 个元素全部丢掉。为什么？假设 A 的第 k//2 个元素更小，这意味着 A 的前 k//2 个元素全都小于等于 A 的第 k//2 个元素，而 B 里至少有 k//2 个元素排在后面。那就至少存在 k//2 个来自 B 的元素，比 A 的前 k//2 个元素都要大，再加上 A 自身的前 k//2-1 个元素，A 的前 k//2 个元素最多只能排到第 k-1 名。所以它们不可能是第 k 小，可以直接出局。

这个逻辑还有一个好处：不必在乎两个数组元素的具体值到底怎么交错，只要抓住“有足够多的元素确定排在它们前面”这一条，删除就是安全的。面试时如果被问到“为什么排除一半不会丢掉中位数”，你只需要把这个推理过程说清楚，通常就能过关。这里我还想强调一个边界：如果某个数组剩余长度不足 k//2，那我们就只能取到它的最后一个元素。如果这个末尾元素依然更小，那整个短数组都可以被排除，此时第 k 小一定在长数组里；反之，如果短数组的末尾元素更大，就说明长数组的前 k//2 个元素可以被排除。无论哪种情况，都要保证“丢弃的元素个数”和“k 减少的个数”严格一致，否则后面的下标会全部错乱。

2.3 k值变化的数学逻辑

写代码的人很容易在 k 的更新上犯错。核心原则一句话：丢掉多少个元素，k 就减多少。为什么？因为第 k 小的定义建立在“当前所有剩余元素”的基础上，一旦当前集合里少了 p 个元素，原来的第 k 小就变成了剩余集合里的第 k-p 小。这就像排队打饭，队伍前面走了 10 个人，你从第 20 位自动变成第 10 位，排名跟着前面人数同步收缩。

理解这个对应关系后，整个循环的结构就清晰了：初始化 k 为中位数的排名；每轮比较后，排除掉较小一侧前 p 个元素，同时令 k -= p；当 k == 1 时，答案就是当前两个数组头部元素里较小的那一个。这些逻辑写成代码一共也就七八行，但想明白“为什么是第 k-p 小”而不是“第 k 小”，才是真正吃透这道题的分水岭。很多人代码背得滚瓜烂熟，一旦被追问 k 为什么变化就打结，多半是这里没打通。

3. 代码实现与逐段解析

3.1 通用解法：递归排除法

直接上能跑的代码，我用 Python 写，逻辑和 C++、Java 完全同构：

def find_median_sorted_arrays(nums1, nums2): def get_kth(k): m, n = len(nums1), len(nums2) i, j = 0, 0 while True: if i == m: return nums2[j + k - 1] if j == n: return nums1[i + k - 1] if k == 1: return min(nums1[i], nums2[j]) half = k // 2 ni = min(i + half, m) - 1 nj = min(j + half, n) - 1 if nums1[ni] <= nums2[nj]: k -= ni - i + 1 i = ni + 1 else: k -= nj - j + 1 j = nj + 1 total = len(nums1) + len(nums2) if total % 2 == 1: return get_kth(total // 2 + 1) else: return (get_kth(total // 2) + get_kth(total // 2 + 1)) / 2

这段代码的骨架是一个 while True 循环，真正的出口只有三个：某个数组被耗尽、k 已缩减到 1、或者在二者都不满足时继续排除。循环里做的事情非常单一：找到两个数组当前的“第 half 个候选元素”（越界就取末尾），比较大小，排除较小一侧的前面部分，同步更新 i 或 j 以及 k。我建议你拿到代码后先不要背，拿一组小例子手动走一遍，比如 nums1=[1,3,5,7,9]，nums2=[2,4,6,8,10]，k 从 5 开始，一步步看它是怎么排除的。很快你会发现，自己已经能预判每一轮的排除方向，那就说明思路真的进脑子了。

3.2 边界条件分析

写这段代码，真正的硬仗在边界。我把最容易翻车的几个点拎出来：

• i == m 或 j == n：说明某个数组已经被全部排除，不需要再比较，答案直接在另一个数组的 j+k-1 或 i+k-1 下标处。
• k == 1：当前两个数组头部较小的一个就是答案，直接返回 min(nums1[i], nums2[j])。
• ni 和 nj 的取值：必须用 min(i+half, m)-1 做截断，保证不越界。哪怕 ni 取到了末尾，排除的元素数量仍然按 ni-i+1 计算。
• 比较符号用 <= 而不是 <：等于时优先排除 nums1 的前段，这样不会漏答案，也不会陷入死循环。

这些细节看上去琐碎，但几乎所有“逻辑看着对、提交就报错”的代码，最后都折在这些地方。我的经验是别在纸上空想，直接找一个奇数长度、一个偶数长度的真实用例，手动跟一遍代码，把 i、j、k 每一步的变化都写下来，比看十篇解析都管用。

3.3 复杂度与运行表现

复杂度这块倒是很干净。每轮循环 k 至少减少 k//2，而 k 的初始值最多是 total//2+1，所以循环轮数是 O(log(m+n)) 级别。每轮只有常数次比较和赋值，总时间复杂度稳定在 O(log(m+n))，空间复杂度 O(1)。实际跑起来，哪怕两个数组长度都到百万级，也就二十多轮循环，肉眼几乎感知不到耗时，这就是 log 级别算法的体感。面试里如果追问“为什么不是 O(log(min(m,n)))”，你可以补充说这是第 k 小模型的通用复杂度，如果要严格依赖较短数组长度去优化，就得换划分数组法了。

4. 实操中会踩的坑

4.1 奇偶情形最容易写错

这题最高频的低级错误，就是只处理奇数情况。不少同学写完直接 return get_kth((total+1)//2)，偶数长度的用例一跑就崩。更隐蔽的是，即使你记得偶数要取平均，也可能把两个 k 写错，正确的是 total//2 和 total//2+1，而不是 total//2-1 这种差一位的下标。判断奇偶用 total % 2 == 1：奇数时中位数是第 total//2+1 个；偶数时取第 total//2 个和第 total//2+1 个的平均。写完代码后，建议用 [1,3] 和 [2,4] 这类小用例测一下，立刻能暴露奇偶问题。

这里我整理一个实用速查表，收藏下来能省不少事：

4.2 数组越界的经典诱因

取第 k//2 个元素时，如果数组长度不够，直接写 nums1[i+half] 必然会越界。这个问题在极端用例下几乎必然出现：比如 nums1 只有 1 个元素，nums2 有几百个元素，此时 half 可能远大于 1 的长度，不限制就崩。解法里用 ni = min(i+half, m)-1 做保护，再配合“末尾元素也被纳入排除”这一逻辑，就能把数组长度差距很大的情况处理干净。很多解法喜欢在某个数组长度不足时走特殊分支，看起来像是在处理“短数组已经用完”，其实本质都是同一个问题：让索引安全落在有效范围内。

4.3 另一种划分法到底该不该学

除了第 k 小思路，这题还有一种主流解法——在较短数组上二分划分点，使两个数组的左侧元素总数恰好等于右侧，再根据分割线附近的四个元素值决定中位数。这种划分法的复杂度可以做到严格的 O(log(min(m,n)))，在追求极致性能的场景下更优。但以我的教学经验，初学阶段不建议直接上手划分法：它的边界比第 k 小更绕，很多人写完根本解释不清“为什么左右两侧数量相等就能确定中位数”。建议先把第 k 小方法写熟，能用 O(log(m+n)) 解决并讲清楚原理，对绝大多数面试场景已经完全够用。划分法等后续想深入时再研究，能少走很多弯路。

4.4 递归写法的坑：栈溢出和重复计算

很多人第一次实现时喜欢用递归，也就是在 get_kth 里递归调用 get_kth(k-half)。单看递归深度，只有 O(log k)，一般不会爆栈，但一旦在递归传参时用了切片（比如 nums1[half:]），复杂度立刻恶化。因为切片本身要拷贝数组，每次递归都会复制一遍剩余元素，空间和时间都变成 O(m+n) 级别，实测会慢一个数量级。正确做法是像上面的代码一样，用 i 和 j 两个指针维护当前范围，而不是真的去“切”数组。这也是我坚持用迭代实现的原因——不是递归不行，而是递归版本一旦处理不好，复杂度会悄悄变质。

5. 延伸思考与面试策略

5.1 同源变体题

吃透这道题，你会发现自己解锁了一串相关问题的通用解法。最直接的就是“在两个有序数组中找第 k 小”，把本题的 get_kth 单独拎出来就是一道独立经典题。再往上，还有“合并 K 个有序数组找中位数”，多路归并场景通常用堆来维护每个数组的候选头部，是另一个热门考点。更远的还有“数据流中找中位数”，需要同时维护一个小顶堆和一个大顶堆，动态保持两部分数量平衡。把这些题放到一起看，能串成一条清晰的知识线：有序结构上的排名查询问题，解法无非是二分排除、堆维护、动态平衡这几类。理解了这题的模型，等于给这条知识线开了一个好头。

5.2 面试表达话术

面试时怎么讲这道题，顺序其实很关键。我推荐的表达结构是：先说明为什么不能直接合并——因为 O(m+n) 不满足题目约束；再抛出第 k 小转化，把中位数定义和 k 的选取一次说清；然后讲每轮为什么能安全排除前 k//2 个元素，用“至少有若干个元素一定排在它们前面”来证明；最后补充边界情况，比如某个数组被耗尽、k=1 时怎么处理。这个顺序好处是层层递进，面试官也容易跟着你的思路走。他们通常会在“安全删除”那里追问一次，你只要把 2.2 节的推理复述一遍，就能证明你是真理解，而不是背答案。我见过不少候选人代码写得飞快，但被问到“为什么排除一半不会丢掉中位数”就卡壳，这个点值得提前练熟。

5.3 实战后的个人建议

最后聊点我实际刷题中的体会。这题我前前后后重写过很多次，每次重写都会发现之前理解的漏洞，最集中的就是“排除数量”和“k 递减数量”的一致性。后来我养成了一个习惯：不管写哪道二分题，都先写一个暴力版本做对拍。比如这题就直接写合并排序，然后把二分版结果和暴力版结果放在几千组随机数组上比对，一旦有不一致，立刻就知道是边界逻辑出了问题。这种方式比对着单个用例死磕高效太多，也非常适合用在其他算法题上。等你真正吃透了第 k 小模型，再回头看这道“寻找两个正序数组的中位数”，它就不再是背不下来的难题，而是一个可以随手迁移的思维工具。