题目

一个长度为 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) 说明你所设计算法的时间复杂度和空间复杂度。

解析

(1) 设计思想

答案：双数组同时折半法——在 A 和 B 各自的当前段中分别取中位数 a = A[m₁]、b = B[m₂] 比较；根据大小关系裁掉两边各 1/2，每轮把搜索范围减半，直到两段各只剩 1 个元素，返回较小者。时间 O(log n)、空间 O(1)。

总长 2n，"中位数"按题面定义是合并升序后的第 ⌈2n/2⌉ = 第 n 个（从 1 起数）。直接合并 O(n) 找第 n 个虽然能解，但有更快的 O(log n) 算法。

为什么折半能成立？

设 A 当前段 、B 当前段 ，两段始终保持等长（这是循环不变量）。各取中位数 、：

• ：这就是合并后的中位数（两段都有同样多元素 ≤ 它）→ 返回；
• ：合并后的中位数不在 A 的左半 + B 的右半——因为 A 的左半 + B 的右半各贡献的元素加起来至多覆盖到中位数之前。具体地：
  • A 左半（不含 ）的元素全都比 a 小，即比 b 小，最多排到合并序列的较前面；
  • B 右半（不含 b）的元素全都比 b 大，最多排到合并序列的较后面；
  • 真正的中位数夹在中间——只能在 A 的右半（含 或不含，看奇偶）+ B 的左半（含 或不含） 里；
• ：对称裁剪——保留 A 的左半 + B 的右半。

奇偶处理（保持两段等长这条不变量）：

• 当前段长 len 为偶数（如 4 → 切 2 + 2）：含中元素的那段从下一个开始，不含中的那段保留含中位置。a < b 时：s1 = m1 + 1（A 切掉左半含中的 m₁）、e2 = m2（B 切掉右半但保留 m₂）；
• 当前段长 len 为奇数（如 5 → 切 2 + 1 + 2）：两段都保留各自的中元素。a < b 时：s1 = m1、e2 = m2。

每轮 len 折半，至多 轮就缩到 len = 1，此时两段各剩 1 个元素，返回 min(A[s1], B[s2])。

例子验证：n = 5，A = (11, 13, 15, 17, 19)，B = (2, 4, 6, 8, 20)，目标中位数 11。

轮	段		比较	操作
1	A[0..4], B[0..4]，len=5 奇		15 > 6
2	A[0..2], B[2..4]，len=3 奇		13 > 8
3	A[0..1], B[3..4]，len=2 偶		11 > 8
4	A[0..0], B[4..4] 退出	—	—	返回 ✓

(2) 代码实现

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];
}

关键点说明：

• 不变量"两段等长"：每轮裁剪后必须保证 ，否则后续 m₁、m₂ 的比较不再对应"全局中位数"。这就是为什么奇偶要分别处理——奇数段切掉的元素数量多 1（含中位置参与缩减）。
• 不要把题目"merge 后取第 n 个"硬上 O(n) 合并：合并法对，但时间和空间都是 O(n)；本题"两方面都尽可能高效"明确指向 O(log n) + O(1) 这个最优解。
• 退出条件：s1 < e1 || s2 < e2 任一段还可缩就继续；都缩到长度 1 才退出。
• 千万别误返回 max：合并后的中位数（第 n 个）小于第 n+1 个，所以两段各剩一个时取 较小者。

(3) 复杂度分析

• 时间复杂度 ：每轮把段长减半，迭代次数 ，循环体内是常数次比较与赋值。
• 空间复杂度 ：仅用 s1, e1, s2, e2, m1, m2, len 几个标量。

编者注（生僻术语）：本题是「两个等长升序序列的中位数」专题，与 leetcode #4「Median of Two Sorted Arrays」（不等长版）属同一思路族。考研只考等长情形——等长时算法干净利落（每轮两段各切一刀），不等长时要先额外处理一个段比另一个段小很多的情况，难度跳跃明显。本题学透"等长"版本，可直接为面试做准备。