刷数据结构题，最怕遇到那种看着有思路、写出来却到处是 bug 的题目，求两个升序序列的中位数就是典型代表。单独看一个有序数组，中位数一句话就能说清；两个升序序列拼在一起，很多人的第一反应是先合并成一个数组再按下标取。这个思路没错，但会错过归并排序里真正值钱的东西。这篇笔记记录的是我从最笨的合并法一路优化到二分切分法的完整过程，适合正在复习数据结构、准备算法面试，或者想把归并排序思想用熟的人。下面三种方法，复杂度从 O(m+n) 空间一路降到 O(1) 空间，最后二分法能做到 O(log min(m,n))，每一层都能看到不同的算法思维。
1. 先别急着写代码，把中位数的定义想清楚
1.1 中位数不是单纯“中间那个数”
单个有序数组的中位数大家都会求：长度为奇数，取正中间那个；长度为偶数，取中间两个的平均值。两个升序序列的中位数，本质上也是把两个数组当成一个合并后的整体，再按同样的规则取。
比如 A = [1, 3, 5, 7]，B = [2, 4, 6, 8, 10]，合并后整体是 [1, 2, 3, 4, 5, 6, 7, 8, 10]，总长度 9，中位数就是第 5 个元素，也就是 5。这里最容易被忽略的是：中位数不一定来自某一个固定的数组，可能来自 A，也可能来自 B，完全取决于两个数组元素穿插后的位置。
所以我在写任何解法前，都会先把两个总长度公式写在草稿纸上：
- 总长度 total = m + n。
- total 为奇数时，合并后下标 total / 2 的元素就是中位数（0-based）。
- total 为偶数时，合并后下标 total / 2 - 1 和 total / 2 的两个元素取平均值。
别小看这两行，后面无论双指针还是二分切分，循环边界全靠它们撑住。很多人代码写错，不是算法思路错，而是“第几个”和“下标几号”换算错了。
1.2 两个升序序列到底藏了什么信息
这道题最关键的前提是“两个序列各自升序”。如果数组是乱序的，那除了全部排序，基本没有更好的办法，复杂度至少是 O((m+n) log(m+n))。但既然各自有序，我们就有了两个可利用的点：
第一，可以直接用归并排序里的 merge 过程，把两个有序序列变成一个新的有序序列，这一步是线性的，不需要再整体排序。第二，既然知道整体是有序的，中位数其实只依赖于整体序列中间位置的少数几个元素，很多中间过程可以忽略，于是才有了后面的双指针和二分优化。
我习惯把这个信息点理解成“题目已经送你一半答案了”：有序性让你不用比较所有元素，只需要在边界处验证几个关键位置之间的关系。这个想法也是第三种二分切分方法的理论基础。
2. 方法一：归并排序里的 merge 就是为这个场景准备的
2.1 把两个有序序列合并成一个有序序列
归并排序大家都不陌生，先把数组拆成两半，递归排序，最后再用 merge 把两个有序数组合并。很多笔记会把归并排序的递归部分讲得很细，但 merge 这个函数本身才是真正的核心。它做的事情很简单：两个指针分别指向两个有序数组的头部，比较当前指到的元素，谁小谁先放入结果数组，然后对应指针后移。
求两个升序序列的中位数，恰好就是这个场景。你不需要对整个大数组排序，只需要把两个已经有序的序列线性合并到一起，合并完成后的数组就是最终有序的整体。这时候取中位数的下标，问题就解决了。
我第一次刷这道题时就是用的这个思路：把归并排序里的 merge 函数原封不动搬出来，先得到一个完整的有序数组，再按奇偶情况取中间值。代码写起来非常直观，几乎不会出逻辑错误，非常适合用来验证自己对归并过程的理解。
2.2 完整实现：合并后直接按下标取中位
用 C++ 写出来大概是这样的：
#include <vector> #include <algorithm> using namespace std; vector<int> mergeTwoSorted(const vector<int>& a, const vector<int>& b) { int i = 0, j = 0; int m = a.size(), n = b.size(); vector<int> c; c.reserve(m + n); while (i < m && j < n) { if (a[i] <= b[j]) { c.push_back(a[i++]); } else { c.push_back(b[j++]); } } while (i < m) c.push_back(a[i++]); while (j < n) c.push_back(b[j++]); return c; } double medianOfTwoSorted1(const vector<int>& a, const vector<int>& b) { vector<int> c = mergeTwoSorted(a, b); int total = c.size(); if (total % 2 == 1) { return c[total / 2]; } return (c[total / 2 - 1] + c[total / 2]) / 2.0; }注意两个细节：
c.reserve(m + n)可以提前分配好内存，减少 vector 扩容带来的开销。- 偶数情况一定要除以
2.0，不是2，否则结果是整数，小数部分直接被截掉。
我一开始写过/2，结果测试用例 [1, 2, 3, 4] 和 [5, 6] 时，正确中位数 3.5 被算成了 3。这种错很隐蔽，因为有些用例恰好是整数结果，你会以为是正确的。
2.3 复杂度与适用场景
方法一的时间复杂度是 O(m+n)，因为要遍历两个数组各一次；空间复杂度是 O(m+n)，因为额外创建了一个完整的结果数组。如果 m+n 是百万级别，内存开销就会比较明显。
它的优点也很突出：
- 思路最直白，归并排序的 merge 函数直接复用。
- 边界问题少，只要 merge 写对，取中位数就只是下标计算。
- 适合快速验证答案，也适合帮助初学者理解归并过程。
缺点则是“杀鸡用了牛刀”。我们明明只想取中间一两个元素，却把整个数组都构造了出来。如果面试官只是问你能不能再优化，这个问题就来了。所以方法一可以作为铺垫，但通常不是最终答案。
3. 方法二：双指针只数到中位，不用真的合并
3.1 把 merge 过程中的“中间两个值”记下来
方法一之所以浪费空间，是因为结果数组里中位数以外的元素暂时都用不到。但仔细想一下，中位数只依赖整体序列中间的一两个位置。我们完全可以模拟 merge 的过程，用两个指针从左往右比较，直到走到中位数所在的位置，同时把上一个元素也记下来，用于偶数情况求平均。
这个方法其实就是方法一的“惰性版本”：指针移动的规则和 merge 完全一样，只是不把每次选中的元素存进数组，而是只在变量里滚动保留前一个值和当前值。等循环结束时，根据 total 的奇偶返回结果。
我把它理解成“边归并边报数”：两个队伍按顺序从小到大排好，你从队头开始喊数，喊到中间那个位置就停下。不需要知道所有队员的名字，只需要记住刚才喊到的两个编号。
3.2 双指针代码与边界判断
实现如下：
double medianOfTwoSorted2(const vector<int>& a, const vector<int>& b) { int m = a.size(), n = b.size(); int total = m + n; int i = 0, j = 0; int prev = 0, cur = 0; for (int step = 0; step <= total / 2; ++step) { prev = cur; if (i < m && (j >= n || a[i] < b[j])) { cur = a[i++]; } else { cur = b[j++]; } } if (total % 2 == 1) { return cur; } return (prev + cur) / 2.0; }这里最关键的是if (i < m && (j >= n || a[i] < b[j]))这个判断。很多人会直接写a[i] < b[j]，但在其中一个数组已经遍历完时，继续访问a[i]或b[j]就会越界。正确写法需要先判断i < m，同时用j >= n表示 b 数组已经走完，此时只能取 a 的当前元素。
另一个容易出错的地方是循环次数。step <= total / 2实际上会执行total / 2 + 1次，对应 0-based 下标total / 2。比如 total = 5，中位数下标是 2，需要取到第 3 个元素，循环 3 次没错。total = 6，中位数是下标 2 和 3 的平均，循环 4 次，最后一次的prev正好是下标 2，cur是下标 3。
3.3 空间省下来了，但代码变“脏”了一点
方法二的时间复杂度仍然是 O(m+n)，但空间复杂度降到了 O(1)，只用了两个临时变量。代价是逻辑没有方法一那么直白，尤其偶数情况下要明白prev的更新时机。
我调试时最多的问题出现在：把prev = cur放在循环最后，而不是下一次循环的开头。这会导致奇数没问题，偶数求平均时prev还是初始化时的 0。正确做法是每次取新元素之前，先把旧值保存下来。这一步一旦写对，方法二的正确率就会很高。
这个方案足够应对大多数笔试场景：代码短，思路简单，空间利用率高。如果面试官没有明确要求优化到对数级别，写出方法二通常已经不错了。但如果你想展示分治思维，就要继续看第三种。
4. 方法三：二分查找切分点，对数时间的中位数解
4.1 换一个角度看中位数
中位数除了“中间那个数”之外，还有一个更本质的理解：把合并后的有序序列切成左右两半，左边元素数量要么等于右边，要么比右边多一个。如果这个切分点找对了，中位数就只取决于切分点左右两侧的少数几个元素。
现在的问题变成了：两个有序数组不合并，我能不能直接找到这个切分点？答案是可以。具体做法是在较短的数组上二分，确定从它左边取多少个元素，然后根据左半部分总数量，自动算出另一个数组的左边要取多少个元素。
可以想象有两列已经按身高排好的队伍，要把它们合成一列并从中间切开。原来两列分别有序，你不需要把所有人数一遍，只需要在每列各选一个切点，保证切点左侧的所有人都比右侧的所有人矮就行。
4.2 确定二分区间和 j 的计算方式
设 A 是较短的数组，长度 m；B 是较长的数组，长度 n，且 m <= n。中位数的左侧元素个数记为 leftCount = (total + 1) / 2，这里 total = m + n，(total + 1) / 2是向上取整后的左半部分数量。
假设在 A 中左侧取 i 个元素，那么 B 中左侧就必须取 j = leftCount - i 个元素。i 的取值范围是 [0, m]，因为 A 最多只能把 m 个元素全部放在左侧。为什么一定要在较短数组上二分？因为 i 的范围越小，二分次数越少，复杂度是 O(log min(m,n))。另一方面，m <= n 时 j 会自动落在 [0, n] 范围内，省掉很多额外判断。
切分点合法的条件有两个：
- A[i-1] <= B[j]，即 A 左边的最后一个元素不能大于 B 右边的第一个元素。
- B[j-1] <= A[i]，即 B 左边的最后一个元素不能大于 A 右边的第一个元素。
如果 A[i-1] > B[j]，说明 A 拿进左侧的元素太多了，i 要向左移动；否则说明 i 还可以向右移动，让左侧包含更多 A 的元素。
这两个条件为什么够用？因为 A 和 B 内部各自有序，所以 A 左侧的所有元素都 <= A[i-1]，B 右侧的所有元素都 >= B[j]，加上跨数组的两个临界条件，就能证明左半部分整体都小于等于右半部分。
4.3 完整代码与边界值处理
边界处理是方法三最容易出错的地方。如果 i = 0，表示 A 左侧一个元素都不取，A[i-1] 不存在，应该视为负无穷；如果 i = m，表示 A 全部在左侧，A[i] 不存在，应该视为正无穷。B 同理。
#include <vector> #include <climits> #include <algorithm> using namespace std; double medianOfTwoSorted3(vector<int>& a, vector<int>& b) { const vector<int>& A = (a.size() <= b.size()) ? a : b; const vector<int>& B = (a.size() <= b.size()) ? b : a; int m = A.size(), n = B.size(); int total = m + n; int leftCount = (total + 1) / 2; int low = 0, high = m; while (low <= high) { int i = low + (high - low) / 2; int j = leftCount - i; int aLeft = (i == 0) ? INT_MIN : A[i - 1]; int aRight = (i == m) ? INT_MAX : A[i]; int bLeft = (j == 0) ? INT_MIN : B[j - 1]; int bRight = (j == n) ? INT_MAX : B[j]; if (aLeft <= bRight && bLeft <= aRight) { if (total % 2 == 1) { return max(aLeft, bLeft); } return (max(aLeft, bLeft) + min(aRight, bRight)) / 2.0; } else if (aLeft > bRight) { high = i - 1; } else { low = i + 1; } } return -1.0; }这里我用了const vector<int>& A和const vector<int>& B来引用较短和较长的数组，没有额外复制数据，所以空间复杂度依然是 O(1)。如果这时候图省事直接按值传参vector<int> a，复制两个数组本身就会把时间拖回 O(m+n)，就谈不上对数复杂度了。
奇数情况下，leftCount 比右侧多一个，中位数就是左半部分的最大值max(aLeft, bLeft)。偶数情况下，左半部分和右半部分数量相等，中位数是max(aLeft, bLeft)和min(aRight, bRight)的平均值。
4.4 为什么这个方法是对的
有人会担心：只检查四个边界值，会不会漏掉中间位置无序的情况？不会。A 和 B 内部各自有序，所以：
- A 左侧的任意元素小于等于 A[i-1]；
- A[i-1] 小于等于 B[j]，所以 A 左侧所有元素小于等于 B[j] 及其右侧所有元素；
- B 左侧的任意元素小于等于 B[j-1]；
- B[j-1] 小于等于 A[i]，所以 B 左侧所有元素小于等于 A[i] 及其右侧所有元素。
这两条合起来，左侧整体一定小于等于右侧整体。也就是说，你虽然只是在边界处做了四次比较，但借助“内部有序”这个前提，实际上已经验证了整个切分的合法性。二分只是用来寻找这个合法切分点，一旦找到，中位数立刻就能算出来。
我一开始看到这个解法觉得像是变魔术，后来自己画了好几组用例，把 i 从 0 到 m 都列出来，手动模拟切分后的左右数组，才真正说服自己。理解这个解法的关键不是背代码，而是画图：把 A 和 B 上下对齐，中间画一条竖线，竖线左侧元素数固定，再看四个边界值是否满足大小关系。
5. 三种方法横向对比：时间、空间、代码量怎么权衡
5.1 复杂度对照表
把三种方法放在同一个表里看会更清楚：
| 方法 | 时间复杂度 | 空间复杂度 | 代码难度 | 易错点 |
|---|---|---|---|---|
| 归并合并数组 | O(m+n) | O(m+n) | 低 | 偶中位数除以 2.0 |
| 双指针滚动变量 | O(m+n) | O(1) | 中低 | 越界判断、prev 更新时机 |
| 二分切分数组 | O(log min(m,n)) | O(1) | 较高 | 边界 INT_MIN/INT_MAX、i 的二分方向 |
面试时如果要求手写完整可运行的代码，方法二通常是性价比最高的选择，既没有方法一的空间浪费，又没有方法三的大量边界条件。我自己在笔试模拟时也经常优先写方法二，因为它的代码量只有十几行，出错概率低。
但如果面试官追问“还能不能更快”，或者题目数据量极大，比如 m 和 n 都到 1e9 级别，那么 O(m+n) 的时间就无法接受，必须用方法三。这时候考察的就是你对“中位数定义”的理解程度，而不仅是编码能力。
5.2 不同场景怎么选
我把选择逻辑整理成几条经验：
- 如果在复习归并排序，方法一值得完整写一遍，重点体会 merge 过程。
- 如果是笔试或线上测评，优先写方法二，不要一上来就啃二分切分。
- 如果是为了准备算法面试，方法三是必须掌握的，因为它是经典的分治优化模型。
- 如果只是想验证某个复杂解法是否正确，可以用方法一当“暴力对拍器”，用随机数组测试方法三的输出是否一致。
我实际练习时常用一个小技巧：写一个暴力解法，再写一个优化解法，在一个循环里生成随机数组，不断比较结果。这个方法能快速暴露二分切分的边界问题，比背测试用例高效得多。
5.3 归并排序的思维起点：merge 只是第一步
回到标题里的那句话：“归并排序你会用了吗？”很多人刷过归并排序，但只记住了递归拆分数组的步骤，忘了 merge 函数才是整个算法最有复用价值的部分。求两个升序序列的中位数，本质上就是一次 merge 过程的变体。双指针法就是 merge 的惰性版本，二分切分法则是 merge 的“整体跳过”版本。
理解了这一点，你会看到归并排序并不只是一段需要背的代码，而是一种“合并有序结构”的思路。之后的链表排序、逆序对计数、甚至外部排序里的多路归并，全都是同一套思想的扩展。所以这道题表面上在求中位数，实际上是在检验你对有序序列合并的理解程度。
6. 调试记录：这些边界坑我基本都踩过
6.1 典型错误与排查快查表
下列问题是我在练习和帮别人 review 代码时反复遇到的，直接总结成一张排查表：
| 错误现象 | 可能原因 | 解决办法 |
|---|---|---|
| 偶中位数结果缺小数 | 除以了整数 2 | 改为除以 2.0 |
| 双指针数组越界 | 没判断一个数组已遍历完 | 条件写 `i < m && (j >= n |
| 奇数长度结果不正确 | 循环次数少了 1 次 | 用step <= total / 2 |
| 二分切分找不到答案 | 没选较短数组进行二分 | 先保证 m <= n |
| 取 A[i] 或 B[j] 越界 | 没有处理 i == m / j == n | 用 INT_MAX 替代 |
| CONTINUE 返回值异常 | 循环结束后强制返回 | 合法解一定存在，返回只是兜底防警告 |
二分切分里最容易搞混的是调整方向：当 A[i-1] > B[j] 时，说明 A 左侧取多了，应该缩小 i，也就是把 high 调到 i-1；反过来当 B[j-1] > A[i] 时，说明 A 左侧取少了，应该增大 i，low 调到 i+1。我自己会因为“左边太大”和“i 太大”之间绕晕，后来干脆固定记一句话：哪边左边的最后一个元素太大，就往相反方向收缩。
6.2 建议准备的一组测试用例
无论用哪种方法，写完后我都建议跑下面这些边界用例，覆盖空数组、奇偶长度、相等元素、一长一短等典型情况：
- A = []，B = [1]，结果 1。
- A = [1, 3]，B = [2]，结果 2。
- A = [1, 2]，B = [3, 4]，结果 2.5。
- A = [1, 3, 5, 7]，B = [2, 4, 6, 8]，结果 4.5。
- A = [1, 2, 3, 4]，B = []，结果 2.5。
- A = [1, 1]，B = [1, 1]，结果 1。
- A = [100]，B = [1]，结果 50.5。
特别注意最后一组：两个数组各只有一个元素，合并后中位数是两者的平均值。很多人在二分切分里会忽略这种两个数组长度都极小的情况，导致 leftCount 和 j 的映射对不上。
6.3 我自己的做题习惯
最后分享一个我自己形成的小习惯：看到“两个有序序列”组合求某个统计量时，先不着急写暴力排序，而是问自己三个问题，能不能用归并的线性推进，能不能只保留中间值，能不能用二分跳过一半元素。这个思考框架其实是从这道题里提炼出来的，后来遇到合并有序链表、求两个有序数组的第 k 小元素、寻找交集等题目，我都沿用了同一套思路。
二分切分法的代码第一次写容易劝退，但只要你把边界条件一个个跑过，后面就会越用越顺。我现在看到求两个升序序列的中位数的题目，已经不需要犹豫，直接在脑子里画出切分线，对着四个边界值做判断就够了。这种熟练程度，靠的并不是死记硬背，而是把归并、双指针、二分这三种层级都亲手写过一遍之后的自然结果。
