如果让我从刷题清单里挑一道“看起来简单、真正写对却很难”的题我会选寻找两个正序数组的中位数。它被挂在数组/链表操作这个分类下面但认真做一遍就会发现它真正考的是二分思想两个有序数组、一个目标值、要求 O(log(mn))。很多人一上来就想到合并数组然后取中间值确实能跑通但离题目的进阶要求差着一整个量级。这篇文章想把这题从头到尾讲透从暴力思路开始到分割线法的完整推导再到 Python 实现和一堆容易踩的坑。适合准备算法面试的开发者也适合刚学完数组和链表、想理解“有序数据 二分”到底怎么发力的朋友。1. 题目解读与核心思路分析1.1 先看清题目到底在问什么题目本身非常简短给定两个大小分别为 m 和 n 的正序升序数组nums1 和 nums2找出并返回这两个正序数组的中位数。进阶要求是算法的时间复杂度达到 O(log(mn))。中位数的定义是如果合并后的序列长度为奇数中位数是最中间那个数如果长度为偶数中位数是中间两个数的平均值。比如nums1 [1,3]nums2 [2]合并后是 [1,2,3]中位数是 2。nums1 [1,2]nums2 [3,4]合并后是 [1,2,3,4]中位数是 (2 3) / 2 2.5。有几个细节容易被忽略。第一数组是“正序”的说明单调不减允许有重复元素这会影响二分时用 还是 。第二m 和 n 可能为 0也就是说其中一个数组可能是空的实现时不能假设两个数组都有元素。第三题目要求的是“中位数”不是“合并后的序列”所以理论上我们不需要真的把两个数组合并出来。1.2 O(mn) 已经不错了为什么还要追求 log先把暴力解法摆出来用双指针同时遍历两个数组边比较边计数走到中间位置时停下来时间复杂度 O(mn)空间复杂度可以做到 O(1)。这个解法本身不算差很多场合下已经能用但它不满足题目的进阶要求。O(mn) 和 O(log(mn)) 的差距在数据量小的时候看不出来。假设两个数组长度都接近 50 万mn 约等于 100 万O(mn) 可能要遍历 100 万个元素而 log₂(100万) 大约是 20也就是说二分法只需要 20 多次迭代。一个是百万级操作一个是几十次操作这就是“有序”这个条件带来的巨大红利。所以这道题真正的核心思路是**不能老老实实合并而是要想办法利用两个数组都已经有序的事实每次砍掉一半不可能成为中位数的区域。**这句话听起来简单实际推导时却有很多细节。2. 两条可走的二分解法路线2.1 路线一转化成“找第 K 小元素”中位数其实可以看成一种特殊形态的“第 K 小元素”。如果总长度是奇数中位数就是第 (mn1)/2 小的元素如果总长度是偶数中位数是第 (mn)/2 小和第 (mn)/2 1 小元素的平均值。所以问题可以转化成在两个有序数组中找第 K 小元素。这个方法的核心步骤是每次比较两个数组中第 k/2 个位置的元素谁更小就说明那一方的前 k/2 个元素绝对不可能是第 K 小可以整块排除掉。排除之后 k 减去排除数量继续在剩余数组中找新的第 K 小。比如 A[1,3,5,7]B[2,4,6,8]要找第 4 小先比较 A[1]3 和 B[1]43 更小排除 A 的前两个元素然后 k 变成 2比较 A 的剩余部分和 B再排除 B 的最小元素最后 k1 时直接取两个数组头部的最小值。这条路线思路比较直接代码量稍大递归或迭代都能写。它的本质是“按数量排除”也被称为双数组第 K 小模板面试时如果先说这个解法面试官通常不会继续追问细节因为代码模板性很强。2.2 路线二分割线法更贴近“中位数”的定义我自己更推荐理解另一种做法分割线法。它直接利用中位数的定义把合并后的有序序列切成左右两半使左边的元素数量等于右边的元素数量总长度为偶数或者比右边多一个总长度为奇数同时保证左边最大值不超过右边最小值。对两个数组分别画一条分割线。设 i 表示 nums1 左边元素的个数j 表示 nums2 左边元素的个数那么必须满足i j (m n 1) / 2这个等式保证了左右两边元素数量符合要求。接下来只要让“左边最大”和“右边最小”满足交叉有序关系分割点就找到了中位数也就能直接算出来。2.3 为什么必须在较短的数组上做二分分割线法只需要在一个数组上二分 i另一个数组的 j 由公式确定。但有一个关键约束我们必须在较短的数组上二分。原因有两个。第一是越界风险。如果在较长的数组上二分 i那么 j totalLeft - i 可能变成负数访问 nums2[j-1] 直接越界。交换两个数组后保证 nums1 的长度 m 小于等于 nums2 的长度 n由于 totalLeft 不会超过 nj 就始终落在合法的 [0, n] 范围内。第二是迭代次数。二分的区间越大需要循环的次数越多。在较短数组上二分复杂度是 O(log(min(m,n)))这比 O(log(mn)) 更紧也一定满足题目的要求。很多实现里第一步就是先做交换这一步不是随手写的而是整个算法安全性的基础。3. 分割线法的完整推导与边界处理3.1 分割条件与四个关键值假设我们当前尝试的 i 是一个候选值那么 j totalLeft - i。为了判断这个分割位置是否合法需要看四个关键值nums1 左半部分的最大值leftMax1 nums1[i-1]当 i 0 时nums1 右半部分的最小值rightMin1 nums1[i]当 i m 时nums2 左半部分的最大值leftMax2 nums2[j-1]当 j 0 时nums2 右半部分的最小值rightMin2 nums2[j]当 j n 时分割线成立需要同时满足两个条件leftMax1 rightMin2leftMax2 rightMin1第一个条件保证 nums1 的左半边不会和 nums2 的右半边交叉第二个条件保证 nums2 的左半边不会和 nums1 的右半边交叉。两个条件同时满足时合并序列的左半部分最大值就是 max(leftMax1, leftMax2)右半部分最小值就是 min(rightMin1, rightMin2)。最终结果根据总长度奇偶决定总长度为奇数中位数 max(leftMax1, leftMax2)总长度为偶数中位数 (max(leftMax1, leftMax2) min(rightMin1, rightMin2)) / 23.2 边界情况用正负无穷打通所有特例代码里最麻烦的是边界条件。i 可能等于 0此时 nums1 左边没有任何元素leftMax1 不存在i 可能等于 m此时 nums1 右边没有任何元素rightMin1 不存在。nums2 的 j 同理。处理方式有两种一种是写一堆 if 判断另一种是引入正负无穷。后者代码更统一逻辑也更清晰leftMax1 不存在时用 float(-inf)这样它永远不会影响 max 的计算也不会破坏 leftMax1 rightMin2 的比较。rightMin1 不存在时用 float(inf)这样它永远不会影响 min 的计算也不会导致条件失败。用正负无穷可以把空数组、单元素数组、完全错开的边界情况全部统一处理。比如 nums1 为空时i 只能是 0最后中位数完全由 nums2 决定代码会自动走到正确分支。3.3 移动方向到底让 i 变大还是变小当分割点不满足条件时需要调整 i。这里必须想清楚方向如果 leftMax1 rightMin2说明 nums1 左半部分取值太大也就是 i 可能取大了需要把搜索区间往左收执行 right i - 1。如果 leftMax2 rightMin1说明 nums2 左半部分取值太大。由于 j totalLeft - i想让 j 变小就必须让 i 变大所以执行 left i 1。这里有一个很有意思的推导两个条件不可能同时被破坏。如果 leftMax1 rightMin2 且 leftMax2 rightMin1 同时成立会推出 leftMax1 rightMin2 rightMin1不对更严谨的推导是leftMax1 rightMin2 leftMax2 rightMin1 leftMax1最终推出 leftMax1 leftMax1矛盾。因为两个数组都是有序的第一个数组的左最大值不可能大于自己的右最小值第二个数组同理。所以两个“需要调整”的方向不会冲突代码里用 if / elif 判断是安全的。3.4 手动推演一个完整例子用 nums1 [1,3,5]nums2 [2,4,6,8,10] 推一遍。m 3n 5m n不需要交换。totalLeft (3 5 1) / 2 4二分 i 在 [0,3] 之间。第一次尝试left 0right 3i 1j 3。leftMax1 nums1[0] 1rightMin1 nums1[1] 3leftMax2 nums2[2] 6rightMin2 nums2[3] 8条件11 8 成立条件26 3 不成立说明 i 太小left i 1 2。第二次尝试left 2right 3i 2j 2。leftMax1 nums1[1] 3rightMin1 nums1[2] 5leftMax2 nums2[1] 4rightMin2 nums2[2] 6条件13 6 成立条件24 5 成立。找到了。总长度 8 是偶数中位数 (max(3, 4) min(5, 6)) / 2 (4 5) / 2 4.5。合并后的序列是 [1,2,3,4,5,6,8,10]中位数确实是 4.5。4. Python 代码实现与逐行讲解4.1 完整代码from typing import List class Solution: def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) - float: m, n len(nums1), len(nums2) # 保证 nums1 是较短的那个数组降低二分范围并避免越界 if m n: nums1, nums2 nums2, nums1 m, n n, m total_left (m n 1) // 2 left, right 0, m while left right: i (left right) // 2 j total_left - i left_max1 nums1[i - 1] if i 0 else float(-inf) right_min1 nums1[i] if i m else float(inf) left_max2 nums2[j - 1] if j 0 else float(-inf) right_min2 nums2[j] if j n else float(inf) if left_max1 right_min2: # i 太大需要减小 right i - 1 elif left_max2 right_min1: # i 太小需要增大 left i 1 else: # 找到正确的分割位置 if (m n) % 2 1: return max(left_max1, left_max2) else: return (max(left_max1, left_max2) min(right_min1, right_min2)) / 2.0 # 理论上到不了这里保留返回值让函数完整 return 0.04.2 核心步骤的“为什么”这段代码看着不长但每一步都有讲究。第一步交换数组是为了让较小的数组作为二分对象。我在 2.3 小节已经解释过这里再强调一次不交换的话j totalLeft - i 很容易变成负数代码直接崩。交换之后二分的区间从 O(mn) 级别直接降到 O(min(m,n)) 级别。total_left 的计算用的是 (m n 1) // 2这是为了保证奇数长度时左边多一个元素。比如 mn5total_left3左边有 3 个元素右边自然有 2 个中位数就是左边最大值。偶数长度时 mn6total_left3左右各 3 个中位数取左最大和右最小的平均值。二分循环使用 left right这是一个闭区间搜索。i 的取值范围是 [0, m]每一轮都会算出一个新的 j不会出现 j 越界的情况。当 left_max1 right_min2 时说明当前 i 不满足条件且 i 偏大直接把右边界收缩到 i-1当 left_max2 right_min1 时说明 i 偏小把左边界推进到 i1。两个判断都用 而不是 是因为数组允许重复元素等于的情况不影响分割的正确性。4.3 测试用例验证我拿几个典型用例跑过这段代码输出都是正确的nums1nums2期望输出合并序列[1,3][2]2.0[1,2,3][1,2][3,4]2.5[1,2,3,4][][1]1.0[1][0,0][0,0]0.0[0,0,0,0][1,2,3][4,5,6]3.5[1,2,3,4,5,6][2][1,3,4]2.5[1,2,3,4]特别是空数组的用例很多实现会单独判断 m 或 n 为零的情况。用正负无穷统一处理之后空数组不需要额外分支代码反而更简洁。4.4 换语言时要留意什么如果你用 C 或 Java 写float(-inf) 要换成 INT_MIN / INT_MAX或者用std::numeric_limitsint::min()这类常量。最需要注意的是最后返回时别把整数除法直接整没了C 里面要写(a b) / 2.0Java 里面可以转成 double 再除。Python 的/本来就算浮点数所以不存在这个问题。5. 实战中的常见问题与排查技巧实录5.1 越界最经典的运行时错误我第一次写这道题时没有做数组交换直接把两个数组扔进二分逻辑结果在 m n 的测试用例上直接下标越界。报错信息指向nums2[j - 1]因为 j 算出来是负数。这个问题排查起来并不难但很容易在面试中当场红脸。解决办法就一条开始前强制保证 nums1 是较短数组。这不只是性能优化更是正确性保证。我之前见过有人用各种花哨的 offset 手段去避免越界最后代码长到根本没法看完全没必要。5.2 死循环left 更新方式用错了另一个高频问题是循环不收敛。最常见的原因是把left i 1写成了left i或者把right i - 1写成了right i。一旦出现这种写法遇到某些输入时二分区间可能永远不会缩小程序就卡死在 while 循环里。判断这个问题的经验是当 i 已经被验证不满足条件时它就不应该再出现在下一次搜索区间里。无论是左边界还是右边界更新时都要让它跨过 i而不是回到 i。另外循环条件用left right配合这种“剔除式”更新比left right更容易推出正确答案。5.3 中位数奇偶算错还有一个容易错的地方是结果计算。有些朋友在奇数的用例下写成min(right_min1, right_min2)结果得到一个完全错误的极小值。记住一个规律由于 total_left 的计算方式是 (mn1)//2奇数长度时左半边永远比右半边多一个元素所以中位数一定落在当前分割线左侧的最大值里。偶数长度时左右数量相等才需要把左侧最大值和右侧最小值放在一起平均。我自己的记忆方法很简单奇数取大偶数取平均。5.4 空数组和单元素数组空数组最容易让代码崩掉但其实分割线法天然能处理。当 nums1 为空时i 只能是 0left_max1 是负无穷最终中位数完全由 nums2 决定。单元素数组也同理比如 nums1[1]nums2 任意i 的可能取值就是 0 或 1所有边界都被 inf 兜住了。写代码时不用为空数组单独写 if但如果面试官问了你可以故意提一句“这里用 inf 统一处理所以不用特判”这会显得你考虑边界很周全。5.5 如果输入换成链表怎么办题目虽然挂在数组/链表操作分类下但输入形态给了数组核心是利用 O(1) 随机访问能力。如果面试官追问“如果输入是链表怎么处理”思路就变了。最简单的做法是先遍历链表把值放到数组里复用这套二分逻辑空间复杂度 O(mn)。链表本身不支持 O(1) 随机访问所以不可能做到 O(log) 级别的查找。遇到这种问题先确认“有序”这个条件还在不在再决定能不能用二分。链表能做的是 O(mn) 的双指针遍历或者单链表逆序、环形链表判断这类典型操作和本题的二分思想不是一回事。6. 从这道题延伸出去的几点思考6.1 数组和链表在算法中的定位差异数组和链表是两类完全不同的数据结构。数组在内存中连续存储可以通过下标 O(1) 访问链表靠指针串联访问第 k 个节点只能从头遍历。这道题的标题里带着“数组/链表操作”但我个人觉得它本质上是一条数组题链表标签更多来自题库的分类习惯。很多热词里出现的“循环单链表”“不带头结点的单链表”“链表遍历”等概念考察的是指针调整和节点操作和这里的二分查找完全是两条路线。做题的时候不要被分类标签带偏看清数据结构的能力边界更重要。数组切片、数组去重这些常见操作也是另一类基本功和二分思维的难点不在一个维度上。6.2 二分查找的“搜索对象”不一定是值这道题给了一个很大的启发二分不一定是对数组元素的值进行二分也可以对“索引位置”“数量划分”进行二分。本题二分的是 i 的值也就是 nums1 左侧元素的个数而不是某个具体数组元素的大小。判断函数则是“当前分割是否满足交叉有序”。遇到类似问题时可以先想清楚三件事搜索空间是什么判断条件是什么方向如何更新。只要搜索空间存在单调性并且能写清楚失败后的移动方向就能套用二分模板。这种思路在更多算法题里都会遇到比如找无序数组中的峰值、在排序数组中找第一个满足某条件的下标等。6.3 我自己在刷题和面试中的一点体会这道题我前前后后写过很多遍每次都有新收获。第一次是在看不懂官方题解的边界推导硬背模板第二次是终于理解了 inf 的作用第三次是自己在白纸上完整推演了一个例子终于知道为什么交换短数组后 j 不会越界。给别人讲算法的时候我的感受是不要一上来就把代码展开。先画一条分割线把两个数组画成上下两排标出 i 和 j再看四个关键值分别是什么。边界图画清楚了代码自然就写出来了。如果你正在准备面试建议至少手写三遍第一遍照着模板第二遍默写第三遍试着改成找第 K 小的写法。三遍之后你才算真正吃透这道题。对于二分查找这个大类我的经验是先明确“搜索区间”和“排除条件”再写循环。左右边界更新时多用显式的left mid 1/right mid - 1避免把已经验证过的位置重新放回搜索区间。这个习惯能帮你避开一大半二分题的死循环和越界问题。