Appearance
2011·42 两个升序序列的中位数：从归并计数到双数组折半
本文属于「从暴力解到最优解」专题。这是 12 道「尽可能高效」真题里唯一一道最优解达到
的——从暴力解的 升级过去，跨过的是一整个数量级。
题目
一个长度为 L（L ≥ 1）的升序序列 S，处在第 ⌈L/2⌉ 个位置的数称为 S 的中位数。例如，若序列 S₁ = (11, 13, 15, 17, 19)，则 S₁ 的中位数是 15。两个序列的中位数是含它们所有元素的升序序列的中位数。例如，若 S₂ = (2, 4, 6, 8, 20)，则 S₁ 和 S₂ 的中位数是 11。
现有两个等长的升序序列 A 和 B，试设计一个在时间和空间两方面都尽可能高效的算法，找出两个序列 A 和 B 的中位数。要求：
(1) 给出算法的基本设计思想。 (2) 根据设计思想，采用 C、C++ 或 Java 语言描述算法，关键之处给出注释。 (3) 说明你所设计算法的时间复杂度和空间复杂度。
题面写了「时间和空间两方面都尽可能高效」——按总纲的分类，暴力解和最优解之间存在真实分差。总分 13 分。
第一步：把暴力解写对
先把「中位数」翻译成可操作的目标：A、B 各长 n，合并后总长 2n，按题面定义中位数是第 ⌈2n/2⌉ = 第 n 个（从 1 起数）。
那最自然的想法就是归并：两个指针分别指向 A、B 的开头，每次取较小者前进一步——这正是归并排序合并阶段的动作。数到第 n 个取走的元素，它就是答案。而且我们只要这个值，不需要合并后的完整序列，所以连结果数组都不用开：
c
int median(int A[], int B[], int n) {
int i = 0, j = 0; // 分别指向 A、B 的当前元素
int cur = 0; // 最近一次被取走的值
for (int k = 0; k < n; k++) { // 归并着数，取满 n 个停
if (A[i] <= B[j])
cur = A[i++]; // A 的当前值更小，取它
else
cur = B[j++];
}
return cur; // 第 n 个被取走的就是中位数
}一个值得写进注释的边界论证：循环体内 i、j 永远不会越界。每取走一个元素，i + j 恰好加 1；循环最多执行 n 次，所以取数前始终有 i + j < n，即 i < n 且 j < n——两个下标都停在各自数组内，连「某一路耗尽」的分支都不需要。
验证题面的例子：A = (11, 13, 15, 17, 19)、B = (2, 4, 6, 8, 20)，归并前 5 步依次取走 2, 4, 6, 8, 11，第 5 个是 11 ✓。
复杂度：一遍归并数 n 步，时间
它值多少分
按正确性/最优性两个维度（详见总纲）：
- 正确性：把题面定义正确翻译成「合并后第 n 个」、归并逻辑对、边界论证清楚、复杂度分析
与实现一致——正确性维度的主体分拿得到。 - 最优性：空间
已经达标；卡在时间上。题面「两方面都尽可能高效」的期望是 ， 归并够不到，时间那一档拿不到。
还有一个更浪费的变体要避开：先把 A、B 完整合并进一个 2n 的辅助数组，再取第 n 个。答案没变，却白花了
暴力解的浪费在哪
用总纲的三个问题审一遍归并计数解：
**有没有重复扫描？**没有，每个元素至多看一次。
**有没有重算已知的东西？**没有。
有没有放着性质不用？——有。A 和 B 都是全局升序的，但归并每次比较只用了「当前两个队头谁小」这一点局部信息，一次比较只淘汰 1 个元素。换个角度看更明显：归并顺带生产了「前 n 个元素的完整出场顺序」，而题目只要第 n 个——为一个值生产了一整段序列，这就是过剩。
升序这个性质其实能让一次比较淘汰半段元素。取 A 当前段的中位数 a、B 当前段的中位数 b（两段始终等长）：
- a == b：两边各有一半元素 ≤ 它，它就是合并后的中位数，直接返回；
- a < b：A 左半的元素全都 ≤ a < b，只能排在合并序列的靠前位置；B 右半的元素全都 ≥ b > a，只能排在靠后位置——真正的中位数被夹在中间，只可能落在「A 的右半 + B 的左半」里，另外那两个半段整段淘汰；
- a > b：对称地保留「A 的左半 + B 的右半」。
一次比较砍掉近一半搜索范围——这就是对数复杂度的来源。
智慧化改造：双数组同时折半
维护 A 的当前段 [s₁..e₁] 和 B 的当前段 [s₂..e₂]，按上面的判定每轮裁剪，直到两段各剩 1 个元素，返回较小者：
c
int median(int A[], int B[], int n) {
int s1 = 0, e1 = n - 1; // A 当前段 [s1..e1]
int s2 = 0, e2 = n - 1; // B 当前段 [s2..e2]
while (s1 < e1 || s2 < e2) {
int m1 = (s1 + e1) / 2;
int m2 = (s2 + e2) / 2;
int len = e1 - s1 + 1; // 当前段长（A 与 B 等长）
if (A[m1] == B[m2]) return A[m1];
if (A[m1] < B[m2]) {
// 中位数在 A 右半 + B 左半
if (len % 2 == 0) { s1 = m1 + 1; e2 = m2; } // 偶：切掉含 m1 的左半
else { s1 = m1; e2 = m2; } // 奇：保留 m1
} else {
// 中位数在 A 左半 + B 右半
if (len % 2 == 0) { e1 = m1; s2 = m2 + 1; }
else { e1 = m1; s2 = m2; }
}
}
// 两段各剩 1 个，较小者就是合并序列的第 n 个
return A[s1] < B[s2] ? A[s1] : B[s2];
}用题面的例子走一遍：n = 5，A = (11, 13, 15, 17, 19)，B = (2, 4, 6, 8, 20)：
| 轮 | 当前段 | 比较 | 裁剪 |
|---|---|---|---|
| 1 | A[0..4], B[0..4]，len=5 奇 | A[2]=15 > B[2]=6 | e₁=2, s₂=2 |
| 2 | A[0..2], B[2..4]，len=3 奇 | A[1]=13 > B[3]=8 | e₁=1, s₂=3 |
| 3 | A[0..1], B[3..4]，len=2 偶 | A[0]=11 > B[3]=8 | e₁=0, s₂=4 |
| 4 | A[0..0], B[4..4]，退出 | — | 返回 min(11, 20) = 11 ✓ |
复杂度：每轮段长减半，迭代次数
从归并解升级过来，这道题的坑比一般的二分密集得多，四个细节决定这 13 分能拿多满：
- 循环不变量「两段始终等长」必须明确陈述并维护。整套判定的合法性建立在它上面：两段等长时，段中位数的比较才对应全局中位数的语义。丢了这条不变量，m₁、m₂ 的比较就漂移了，按算法错处理。
- 奇偶必须分开切。这是等长不变量的技术保障：段长为偶时，含中位数下标的那一半整段切掉（含中元素也丢），不含中的那段保留含中位置；段长为奇时两段都保留各自的中元素。不分奇偶（全部 m+1 或全部 m）会让两段长度错开，后续判定全部失效。
- 退出条件是
s1 < e1 || s2 < e2——任何一段还能缩就继续。写成&&会在一段先缩到 1 时提前退出，另一段还没缩完。 - 终态返回较小者。合并后的第 n 个小于第 n+1 个，两段各剩 1 个时答案是
min(A[s1], B[s2])——返 max 是这道题的经典错点，一字之差按错处理。另外 a == b 的分支要立刻返回，它已经是答案。
两版对照跑一遍
同一组输入 A = [11, 13, 15, 17, 19]、B = [2, 4, 6, 8, 20]（答案 11），先看归并计数版——逐个取走、一步淘汰一个元素：
再看双数组折半版——每轮一次比较砍掉两个半段，几步就收敛：
演示为 JavaScript 版本，逻辑与上文 C 代码一一对应。
等价方法与升级空间
- 归并计数是这道题公认的保底解：思路正确、空间
，只丢时间档。考场上折半的奇偶细节没把握时，交一份写对的归并远好过交一份切法写错的折半——后者连正确性都保不住。 - 先合并进辅助数组再取第 n 个：同为
时间却多花 空间，是暴力里更差的一档，没有任何理由选它。 - 升级空间：本题是「两个有序数组找第 k 个」问题族的等长特例——等长让算法格外干净，每轮两段各切一刀。它的不等长推广（任意长度的两个有序数组求中位数）要先处理段长悬殊的情况，难度陡增；学透等长版的「比较段中位数、整段淘汰」思想，是啃下推广版的最短路径。
下一步
- 在 OJ 上把两版代码都提交跑一遍：ds-2011-42 两个升序序列的中位数
- 回到题库看这道题的完整解析与错因：真题库 · 数据结构