企业官网建设流程全解析

写这题的人不少,但大部分解答默认你已经懂"二分"了。今天我想换个讲法：先老老实实把题目翻译成人话，再讲一个"笨办法"热身，最后才讲面试官真正想看的二分写法。每一步都拆到你能跟着落地，而不是看个热闹。

1. 题目到底在说什么：先理清"中位数"和"正序数组"

1.1 中位数的精确定义，别再用"最中间那个数"糊弄自己

LeetCode第4题的原问题描述很简单：给两个升序排列的数组 nums1 和 nums2，要你找出这两个数组合并后的中位数，要求时间复杂度 O(log(m+n))。

很多人栽在第一步：没搞清楚"中位数"在偶数长度下的处理方式。如果只在奇数长度数组里找中间那个数，偶数长度就会懵。我直接给你结论：

• 如果总长度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，中位数是(2+3)/2 = 2.5。注意这里有个细节：如果两个数组都是空数组怎么处理？题目通常给的是非空数组，但你自己测试时最好也处理掉。

还有一个容易被忽略的点："正序数组"指的就是升序数组，不是乱序，也不是降序。这个前提是后面所有加速写法的命根子，如果题目换成"无序"，那解法整个就变了。

1.2 为什么这道题能让大多数人卡住

你觉得这题难，不是因为中位数概念复杂，而是因为"O(log(m+n))"这个要求卡死了大部分人的思路。

如果你没有这个复杂度限制，最简单的做法是：把两个数组合并、排序、然后按下标取中位数。这是O(m+n)的归并思路，很多人想得到但不敢写，觉得面试官要的肯定不是这个。而如果你真的直接合并排序（调用语言内置sort），那复杂度就是O((m+n)log(m+n))，在某些公司面试里可能直接被挂。

所以这道题真正的难点是：两个数组本身已经有序，怎么利用"有序"这个信息，把查找范围每次砍半？这就要引出二分思想。但要理解二分，我建议你先从"归并"这个笨办法往下写一遍，感受一下数组有序带来的直觉，再切到二分，会顺很多。

2. 笨办法也是办法：归并合并的完整推演

2.1 合并两个有序数组，时间复杂度O(m+n)的写法

写归并之前，先明确一件小事：两个数组各自有序，合并时不需要对整个大数组重新排序，只需要两个指针从各自头部往右移动，每次取较小值放入结果数组，这条思路就是归并排序里的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当前要比较的位置，循环结束条件是不可能同时走到两个数组末尾。每循环一次，至少有一个指针前进一位，所以最多循环m+n次，时间复杂度是O(m+n)。

但这里有个优化点：其实并不需要真的把整个merged数组建出来。我们只需要中位数，而中位数只关心总长度的中间位置。所以可以让循环只跑到total//2 + 1的位置就停止，沿途记录最后两个数即可。这样空间复杂度能从O(m+n)降到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(m+n)降到O(log(m+n))了。这就是后面要讲的核心思路。

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 最多到 m+n，整体复杂度就是 O(log(m+n))。

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。

由于左半边总数固定，一旦定了i，j就是(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(vector<int>& nums1, vector<int>& 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; // 理论上不会走到这里 }

有几个点我特别想提醒：

1. 为什么nums1必须是较短数组：因为我们在nums1长度范围内二分i，而j = leftCnt - i有可能变成负数。如果n1 <= n2，并且我们从i=0开始，那么j <= leftCnt <= (n1+n2+1)/2，在n1较短时通常不会导致j越界。严格证明有点繁琐，但实践上这是稳妥前提。如果你非要在长数组上二分，边界处理会让人头皮发麻。

2. 奇数个数时左半边多放一个元素：leftCnt = (total+1)/2这个写法，当 total 为奇数时，leftCnt 是(total+1)//2，比如 total=5 时 leftCnt=3，左半边有3个元素，中位数就是左半边的最大值。当 total 为偶数时，leftCnt=total/2，两边一样多，中位数是左最大和右最小的平均。

3. INT_MIN/INT_MAX的用法：这些是虚拟边界。i=0意思是 nums1 左半边没有元素，那nums1LeftMax就是负无穷，任何数都比它大，所以条件一定满足。同理i=n1意思是 nums1 右半边没有元素，那nums1RightMin是正无穷。这是代码不崩的关键。

4.4 手动跑一个例子，把二分过程看清楚

我用一个不对称样例来走查：nums1 = [2, 3, 4]，nums2 = [1, 5, 6, 7, 8]。

n1=3，n2=5，total=8，leftCnt=4。

第一轮：low=0, high=3, i=1, j=4-1=3。

• 分割线：nums1 左半边[2]，右半边[3,4]；nums2 左半边[1,5,6]，右半边[7,8]。
• nums1LeftMax=2，nums2RightMin=7，满足；
• nums2LeftMax=6，nums1RightMin=3，不满足。因为6 > 3，说明 nums2 左边太大了，应该减小j，也就是要增大i。于是low = i+1 = 2。

第二轮：low=2, high=3, i=2, j=4-2=2。

• 分割线：nums1 左半边[2,3]，右半边[4]；nums2 左半边[1,5]，右半边[6,7,8]。
• nums1LeftMax=3，nums2RightMin=6，满足；
• nums2LeftMax=5，nums1RightMin=4，不满足。因为5 > 4，nums2左边还是大了，继续增大i，low=i+1=3。

第三轮：low=3, high=3, i=3, j=4-3=1。

• 分割线：nums1 全部在左半边[2,3,4]，右半边空；nums2 左半边[1]，右半边[5,6,7,8]。
• nums1LeftMax=4，nums2RightMin=5，满足；
• nums2LeftMax=1，nums1RightMin=INT_MAX，满足。

找到分割线，total=8为偶数，所以中位数是：

• 左最大 =max(4, 1) = 4
• 右最小 =min(INT_MAX, 5) = 5
• 结果 =(4+5)/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里用(a+b)//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开始容易把人绕晕

这是纯小白最痛苦的环节。我有一个自己的小方法：写代码前先在纸上给每个边界值做一次"左右空半区"检查。i=0时左半边无元素，j=leftCnt，这时 nums2 的左半边恰好是前leftCnt个元素；i=n1时 nums1 全部在左边，那么 nums2 左边只有leftCnt-n1个元素。每个边界想清楚再写代码。还有一个小经验：所有下标相关的代码，先写注释描述它的物理含义，再写实现，能大幅减少低级错误。

6. 再往前走一步：这道题的变体与面试表达建议

6.1 变体一：如果两个数组长度相同，能不能特殊处理

有面试官会追问：如果 m==n，有没有更简单的解？这本质上是"寻找两个等长有序数组的上中位数"问题，可以在类似二分框架下做，也可以用"比较两个数组中间元素"的方式实现 O(log n)。思路是：取 nums1 的中位数 a，nums2 的中位数 b。如果 a==b，答案就是a；如果 a<b，说明合并后的中位数一定在 nums1 右半边和 nums2 左半边之间，递归缩小区间。这个变体不需要记额外代码，理解了分割线思路后可以现场推导。

6.2 变体二：找第k小，而不是中位数

很多高级算法题（比如"在两个有序矩阵中找第k小"）都是第4题思路的延伸。我建议你把findKth这个函数单独抽出来记住，它比"只写过一遍中位数代码"有价值得多。因为中位数只是第k小的一个特例，真正通用的是排除法。我面试时，遇到类似问题会先说"这个可以抽象成找第k小的问题"，然后画出排除示意图，明显感觉到面试官认可这种表达方式。

6.3 面试时怎么表达自己的思路

我自己的面试表达顺序是：

1. 先说最简单情况：如果不要求复杂度，O(m+n)的归并怎么做，代码几秒钟能写出来。
2. 再说优化方向：因为两个数组各自有序，可以利用"排除k/2个元素"的思路，逐步把搜索范围减半。
3. 最后表明"我可以用递归版本更清晰地表达逻辑，也可以直接写二分版本"。

这样做的好处是：万一你紧张忘记二分实现，至少能先写一个能跑的O(m+n)版本保底，然后向面试官解释为什么它不满足复杂度要求，并展示思路方向。实际面试中，这个谈话过程比默写代码更重要。

6.4 个人练习心得：这题值得刷三遍

第一遍：直接看答案，理解归并版本，然后把 merge 过程亲手敲一遍。第二遍：不看答案，尝试用递归findKth写一遍；这个版本代码短，很适合培养"排除法"思维。第三遍：不看答案，手写二分分割线版本，并且跑通至少5个边界样例。

为什么刷三遍？因为第一遍你是在"读题"，第二遍是在"理解思路"，第三遍才能真正内化边界处理。很多LeetCode题刷一遍会忘，但这道题的核心思路一打通，好多涉及有序数组 + log复杂度的题目（比如LeetCode 33、74、240、378）都会突然变简单。我至今面试时，聊到算法题，仍然会把这道题的分割线画在纸上，因为它是二分思想在数组题里的顶峰案例。

最后说点接地气的感受：LeetCode第4题被归类为"困难"，其实它难在理解"为什么这么二分"，而不是代码本身。你不妨慢下来，先动手把归并版写对，再一步步过渡到二分版。每写一遍，你对"有序数组"二分查找的感觉就会深一层；等到哪天真能在白板上不卡壳地跑通这段逻辑，你会发现自己对所有"局部有序"类题目的理解都上了一个台阶。