写这题的人不少,但大部分解答默认你已经懂二分了。今天我想换个讲法先老老实实把题目翻译成人话再讲一个笨办法热身最后才讲面试官真正想看的二分写法。每一步都拆到你能跟着落地而不是看个热闹。1. 题目到底在说什么先理清中位数和正序数组1.1 中位数的精确定义别再用最中间那个数糊弄自己LeetCode第4题的原问题描述很简单给两个升序排列的数组 nums1 和 nums2要你找出这两个数组合并后的中位数要求时间复杂度 O(log(mn))。很多人栽在第一步没搞清楚中位数在偶数长度下的处理方式。如果只在奇数长度数组里找中间那个数偶数长度就会懵。我直接给你结论如果总长度totalLen是奇数中位数是合并后数组第totalLen/2 1个元素从1开始数如果总长度是偶数中位数是合并后数组第totalLen/2个元素和第totalLen/2 1个元素的平均值。比如nums1 [1, 3]nums2 [2]合并后是[1, 2, 3]中位数就是 2。再比如nums1 [1, 2]nums2 [3, 4]合并后是[1, 2, 3, 4]总长度是4中位数是(23)/2 2.5。注意这里有个细节如果两个数组都是空数组怎么处理题目通常给的是非空数组但你自己测试时最好也处理掉。还有一个容易被忽略的点正序数组指的就是升序数组不是乱序也不是降序。这个前提是后面所有加速写法的命根子如果题目换成无序那解法整个就变了。1.2 为什么这道题能让大多数人卡住你觉得这题难不是因为中位数概念复杂而是因为O(log(mn))这个要求卡死了大部分人的思路。如果你没有这个复杂度限制最简单的做法是把两个数组合并、排序、然后按下标取中位数。这是O(mn)的归并思路很多人想得到但不敢写觉得面试官要的肯定不是这个。而如果你真的直接合并排序调用语言内置sort那复杂度就是O((mn)log(mn))在某些公司面试里可能直接被挂。所以这道题真正的难点是两个数组本身已经有序怎么利用有序这个信息把查找范围每次砍半这就要引出二分思想。但要理解二分我建议你先从归并这个笨办法往下写一遍感受一下数组有序带来的直觉再切到二分会顺很多。2. 笨办法也是办法归并合并的完整推演2.1 合并两个有序数组时间复杂度O(mn)的写法写归并之前先明确一件小事两个数组各自有序合并时不需要对整个大数组重新排序只需要两个指针从各自头部往右移动每次取较小值放入结果数组这条思路就是归并排序里的merge过程。我直接给一段清晰的Python代码def findMedianSortedArrays_merge(nums1, nums2): merged [] i, j 0, 0 m, n len(nums1), len(nums2) while i m and j n: if nums1[i] nums2[j]: merged.append(nums1[i]) i 1 else: merged.append(nums2[j]) j 1 # 把剩余元素全部接上 if i m: merged.extend(nums1[i:]) if j n: merged.extend(nums2[j:]) total m n mid total // 2 if total % 2 1: return merged[mid] else: return (merged[mid - 1] merged[mid]) / 2这段代码的核心操作是两个指针i、j分别指向nums1和nums2当前要比较的位置循环结束条件是不可能同时走到两个数组末尾。每循环一次至少有一个指针前进一位所以最多循环mn次时间复杂度是O(mn)。但这里有个优化点其实并不需要真的把整个merged数组建出来。我们只需要中位数而中位数只关心总长度的中间位置。所以可以让循环只跑到total//2 1的位置就停止沿途记录最后两个数即可。这样空间复杂度能从O(mn)降到O(1)时间复杂度不变。def findMedianSortedArrays_merge_opt(nums1, nums2): m, n len(nums1), len(nums2) total m n target total // 2 # 需要跑到第target个下标从0开始 i, j 0, 0 prev, cur 0, 0 for idx in range(target 1): prev cur if i m and (j n or nums1[i] nums2[j]): cur nums1[i] i 1 else: cur nums2[j] j 1 if total % 2 1: return cur else: return (prev cur) / 2这段代码为什么用j n这个条件因为当j已经越界时后面只剩nums1的元素可取必须强制取nums1当i没越界且nums1[i]更小或相等时也取nums1否则取nums2。这个越界优先判断的思路在二分写法里同样重要。2.2 从归并到二分的思维转折点写归并版不是为了交差而是为了做一件关键的事理解两个数组各自有序这个前提让我们能在取数时精准知道下一个数来自谁。如果你继续深想一步归并是每步排除掉一个不可能是中位数的数二分则是每步排除掉一整个区间。举个例子两个数组长度分别是m和n假如我们知道中位数是合并后第k小的数那么能不能在某个数组里一次性排除掉最小的k/2个元素呢如果能那每轮搜索范围就砍半复杂度就从O(mn)降到O(log(mn))了。这就是后面要讲的核心思路。3. 二分优化的核心思想把问题抽象成第k小3.1 为什么转化到第k小会更好用我们回头看中位数的定义奇数时是第total//2 1个数偶数时是第total//2和第total//2 1个数的平均。如果定义findKth(k)表示两个数组合并后第k小的数k从1开始那么total为奇数时中位数就是findKth(total//2 1)total为偶数时中位数是(findKth(total//2) findKth(total//2 1)) / 2。这样把原问题拆成小问题后我们只需要实现一个findKth函数剩下的就是对这个函数的性能优化。这也是面试时很好的表述路径先转化问题再优化解法评委能明显看到你的思路递进。3.2 每轮排除k/2个元素的原理假设我们要在两个升序数组里找第k小的数。既然是升序那每个数组的前k个元素里必有猫腻。我们可以取nums1的第k/2个元素下标k/2 - 1和nums2的第k/2个元素来比较。这里的关键推理是如果nums1[k/2 - 1] nums2[k/2 - 1]那么nums1的前k/2个元素永远不可能是第k小的数直接排除掉反之排除nums2的前k/2个元素。为什么敢这么排除我用反证法给你解释假设nums1的前k/2个元素里有第k小的数它们每个都小于等于nums1[k/2 - 1]。而nums1[k/2 - 1]又小于等于nums2[k/2 - 1]nums2自己在它前面的元素有(k/2 - 1)个加上 nums1 的前k/2个最多有多少个比nums1[k/2 - 1]小或相等的元素这是一个经典的计数排除法nums1前 k/2 个元素里最多有 k/2 个不大于它nums2前 k/2-1 个元素里最多有 k/2-1 个不大于它因为下标从0到 k/2-2一共 k/2-1 个因此比它小的元素最多只有(k/2 - 1) (k/2 - 1) k - 2个这还不够让它的排名到第k位。所以它连第k-1都不一定排得上更不可能是第k小。于是这 k/2 个元素可以安全删除。这个排除逻辑是整个二分查找的基石看懂了这一步后面的代码全都是套路。3.3 递归边界当某个数组变空或者k变成1递归排除时会出现三种边界情况必须单独处理否则代码会越界如果nums1已经被排除空了直接返回nums2[k-1]如果nums2被排除空了直接返回nums1[k-1]如果k 1直接返回min(nums1[0], nums2[0])因为第1小就是两个数组当前头元素里较小的那个。处理取第k/2个元素时可能越界的问题常见的做法是min(k//2, len(nums1))。比如 nums1 太短连k/2个元素都没有那我们就一次性排除掉整个 nums1取它最后一个元素来比较。这不会破坏逻辑如果 nums1 全部元素都被排除说明第k小的数一定在 nums2 里剩下的递归会自然收敛。下面给一段 Python 实现递归式思路最好懂def findKth(nums1, nums2, k): if len(nums1) 0: return nums2[k - 1] if len(nums2) 0: return nums1[k - 1] if k 1: return min(nums1[0], nums2[0]) idx1 min(k // 2, len(nums1)) idx2 min(k // 2, len(nums2)) if nums1[idx1 - 1] nums2[idx2 - 1]: return findKth(nums1[idx1:], nums2, k - idx1) else: return findKth(nums1, nums2[idx2:], k - idx2) def findMedianSortedArrays(nums1, nums2): total len(nums1) len(nums2) if total % 2 1: return findKth(nums1, nums2, total // 2 1) else: return (findKth(nums1, nums2, total // 2) findKth(nums1, nums2, total // 2 1)) / 2这样写每轮递归都会把 k 至少减半实际上扣除的是min(k//2, len)个元素所以递归深度是 O(log k)而 k 最多到 mn整体复杂度就是 O(log(mn))。4. 直接切两半的二分法不用递归找第k小4.1 这个思路和上一节有什么不同第3节的方法比较好理解但每次递归都要创建新数组切片在Python里切片是O(len)的实际耗时并不好看。如果不想递归也不想切片面试官更常期待你掌握另一种思路直接在一个较短的数组上二分找到分割线的位置。这个方法的核心是不直接找第k小的数而是假装把两个数组从某个位置切开左半边是一个虚拟大数组的左半右半边是虚拟大数组的右半。只要我们保证左半边的所有元素都小于等于右半边的所有元素左半边元素个数正好是总长度的一半或一半多一个。那么中位数就藏在分割线两侧。4.2 分割线怎么找变量的含义先说清楚规定nums1是较短的数组nums2是较长的数组这样做的原因后面会讲。假设n1 len(nums1)n2 len(nums2)total n1 n2我们想在nums1中选下标i作为分割点也就是nums1[0..i-1]属于左半边nums1[i..n1-1]属于右半边在nums2中选下标j使得左半边总个数等于(total 1) // 2。由于左半边总数固定一旦定了ij就是(total 1) // 2 - i。这就是为什么可以在一个数组里二分找i找对了j自动确定。关键判断条件左半边的最大值必须小于等于右半边的最小值。写成代码就是nums1[i-1] nums2[j] nums2[j-1] nums1[i]如果nums1[i-1] nums2[j]说明nums1左边有一些元素太大应该把i往左移动也就是把nums1分割线往左移把更多元素分给右半边。 如果nums2[j-1] nums1[i]说明nums2左边有一些元素太大应该把i往右移动好让j变小从而把nums2左边的一部分元素移到右半边。这里要解释一下边界值i 0表示nums1整个都在右半边i n1表示整个都在左半边。j同理。代码里处理越界时通常用-inf和inf来代表不存在的半边元素。4.3 标准实现与我的避坑注释下面是C写法也是面试手撕最常见的版本double findMedianSortedArrays(vectorint nums1, vectorint nums2) { if (nums1.size() nums2.size()) { nums1.swap(nums2); // 保证 nums1 是较短的数组 } int n1 nums1.size(), n2 nums2.size(); int total n1 n2; int leftCnt (total 1) / 2; // 左半边元素个数奇数时左半边多一个 int low 0, high n1; while (low high) { int i (low high) / 2; int j leftCnt - i; int nums1LeftMax (i 0) ? INT_MIN : nums1[i - 1]; int nums1RightMin (i n1) ? INT_MAX : nums1[i]; int nums2LeftMax (j 0) ? INT_MIN : nums2[j - 1]; int nums2RightMin (j n2) ? INT_MAX : nums2[j]; if (nums1LeftMax nums2RightMin nums2LeftMax nums1RightMin) { // 分割线恰好合适 if (total % 2 1) { return max(nums1LeftMax, nums2LeftMax); } else { return (max(nums1LeftMax, nums2LeftMax) min(nums1RightMin, nums2RightMin)) / 2.0; } } else if (nums1LeftMax nums2RightMin) { high i - 1; // nums1 左边太大把 i 左移 } else { low i 1; // nums2 左边太大把 i 右移 } } return 0.0; // 理论上不会走到这里 }有几个点我特别想提醒为什么nums1必须是较短数组因为我们在nums1长度范围内二分i而j leftCnt - i有可能变成负数。如果n1 n2并且我们从i0开始那么j leftCnt (n1n21)/2在n1较短时通常不会导致j越界。严格证明有点繁琐但实践上这是稳妥前提。如果你非要在长数组上二分边界处理会让人头皮发麻。奇数个数时左半边多放一个元素leftCnt (total1)/2这个写法当 total 为奇数时leftCnt 是(total1)//2比如 total5 时 leftCnt3左半边有3个元素中位数就是左半边的最大值。当 total 为偶数时leftCnttotal/2两边一样多中位数是左最大和右最小的平均。INT_MIN/INT_MAX的用法这些是虚拟边界。i0意思是 nums1 左半边没有元素那nums1LeftMax就是负无穷任何数都比它大所以条件一定满足。同理in1意思是 nums1 右半边没有元素那nums1RightMin是正无穷。这是代码不崩的关键。4.4 手动跑一个例子把二分过程看清楚我用一个不对称样例来走查nums1 [2, 3, 4]nums2 [1, 5, 6, 7, 8]。n13n25total8leftCnt4。第一轮low0, high3, i1, j4-13。分割线nums1 左半边[2]右半边[3,4]nums2 左半边[1,5,6]右半边[7,8]。nums1LeftMax2nums2RightMin7满足nums2LeftMax6nums1RightMin3不满足。因为6 3说明 nums2 左边太大了应该减小j也就是要增大i。于是low i1 2。第二轮low2, high3, i2, j4-22。分割线nums1 左半边[2,3]右半边[4]nums2 左半边[1,5]右半边[6,7,8]。nums1LeftMax3nums2RightMin6满足nums2LeftMax5nums1RightMin4不满足。因为5 4nums2左边还是大了继续增大ilowi13。第三轮low3, high3, i3, j4-31。分割线nums1 全部在左半边[2,3,4]右半边空nums2 左半边[1]右半边[5,6,7,8]。nums1LeftMax4nums2RightMin5满足nums2LeftMax1nums1RightMinINT_MAX满足。找到分割线total8为偶数所以中位数是左最大 max(4, 1) 4右最小 min(INT_MAX, 5) 5结果 (45)/2 4.5验证一下两个数组合并排序后[1,2,3,4,5,6,7,8]中位数确实是4.5。走完这个例子你应该能直观感受到为什么i的移动方向能左右j因为j由leftCnt-i决定i越大j越小这是理解二分方向的关键。5. 面试和做题时最容易踩的中位数坑5.1 空数组与一长一短题目没说数组一定非空所以你测试时最好主动跑几个极端用例。实际我刷题时至少三次因为没处理空数组导致索引越界。比如nums1 []nums2 [1]正常逻辑应该直接返回1。用第3节的递归法第一行if len(nums1)0就能接住用第4节的二分法需要确保n1可以为0分割线二分完全在 nums2 上走也能跑通。我的建议面试时先口头确认输入范围如果对方说可能为空那先处理空数组是必要的防御。5.2 结果必须是浮点数不是整数LeetCode里如果是偶数情况返回值是double。很多人第一次写直接在Python里用(ab)//2直接喜提错误。正确写法是除以2.0或使用括号平均C里两个int相加再除以2如果没加.0结果是整数除法直接丢精度。我见过一个同学在LeetCode在线编译器上排查了十分钟才发现是这个低级问题。5.3 关于int溢出如果你在C里写low high直接除2在极端情况下数组长度接近 INT_MAX 时可能溢出虽然面试题很少考这么极端但标准写法应该是low (high - low) / 2。同理(total 1) / 2在 total 为 INT_MAX 时也可能溢出不过实际题目的数据规模下基本不会但我要提醒你保持良好的习惯。Python用户不需要担心溢出但C面试需要注意。5.4 为什么数组下标从0开始容易把人绕晕这是纯小白最痛苦的环节。我有一个自己的小方法写代码前先在纸上给每个边界值做一次左右空半区检查。i0时左半边无元素jleftCnt这时 nums2 的左半边恰好是前leftCnt个元素in1时 nums1 全部在左边那么 nums2 左边只有leftCnt-n1个元素。每个边界想清楚再写代码。还有一个小经验所有下标相关的代码先写注释描述它的物理含义再写实现能大幅减少低级错误。6. 再往前走一步这道题的变体与面试表达建议6.1 变体一如果两个数组长度相同能不能特殊处理有面试官会追问如果 mn有没有更简单的解这本质上是寻找两个等长有序数组的上中位数问题可以在类似二分框架下做也可以用比较两个数组中间元素的方式实现 O(log n)。思路是取 nums1 的中位数 anums2 的中位数 b。如果 ab答案就是a如果 ab说明合并后的中位数一定在 nums1 右半边和 nums2 左半边之间递归缩小区间。这个变体不需要记额外代码理解了分割线思路后可以现场推导。6.2 变体二找第k小而不是中位数很多高级算法题比如在两个有序矩阵中找第k小都是第4题思路的延伸。我建议你把findKth这个函数单独抽出来记住它比只写过一遍中位数代码有价值得多。因为中位数只是第k小的一个特例真正通用的是排除法。我面试时遇到类似问题会先说这个可以抽象成找第k小的问题然后画出排除示意图明显感觉到面试官认可这种表达方式。6.3 面试时怎么表达自己的思路我自己的面试表达顺序是先说最简单情况如果不要求复杂度O(mn)的归并怎么做代码几秒钟能写出来。再说优化方向因为两个数组各自有序可以利用排除k/2个元素的思路逐步把搜索范围减半。最后表明我可以用递归版本更清晰地表达逻辑也可以直接写二分版本。这样做的好处是万一你紧张忘记二分实现至少能先写一个能跑的O(mn)版本保底然后向面试官解释为什么它不满足复杂度要求并展示思路方向。实际面试中这个谈话过程比默写代码更重要。6.4 个人练习心得这题值得刷三遍第一遍直接看答案理解归并版本然后把 merge 过程亲手敲一遍。第二遍不看答案尝试用递归findKth写一遍这个版本代码短很适合培养排除法思维。第三遍不看答案手写二分分割线版本并且跑通至少5个边界样例。为什么刷三遍因为第一遍你是在读题第二遍是在理解思路第三遍才能真正内化边界处理。很多LeetCode题刷一遍会忘但这道题的核心思路一打通好多涉及有序数组 log复杂度的题目比如LeetCode 33、74、240、378都会突然变简单。我至今面试时聊到算法题仍然会把这道题的分割线画在纸上因为它是二分思想在数组题里的顶峰案例。最后说点接地气的感受LeetCode第4题被归类为困难其实它难在理解为什么这么二分而不是代码本身。你不妨慢下来先动手把归并版写对再一步步过渡到二分版。每写一遍你对有序数组二分查找的感觉就会深一层等到哪天真能在白板上不卡壳地跑通这段逻辑你会发现自己对所有局部有序类题目的理解都上了一个台阶。