[考研算法] 002-寻找中位数

所有的考研题目，为了考试的统一性和易学性，均采用 C 语言来编写，版本为 C17，使用其他版本也可以，仅仅停留在算法层面，各大版本几乎区别不大

题目

2021年统考真题

一个长度为 $L(L>=1)$ 的升序序列 $S$ ，处在第 $\lceil L/2 \rceil$ 个位置的数成为 $S$ 的中位数。
例如，若序列 $S_1=(11,13,15,17,19)$ ，则 $S_1$ 的中位数是 $15$ ，两个序列的中位数是含它们所有元素的升序序列的中位数。
例如，若 $S_2=(2,4,6,8,20)$ ，则 $S1$ 和 $S_2$ 的中位数是 $11$ 。现在有两个等长升序序列 $A$ 和 $B$ 。
是设计一个时间和空间方面都尽可能高效的算法，找出两个序列 $A$ 和 $B$ 的中位数。

分析

题目分析

题中说，两个升序序列，长度相等且都为 $L$ ，且 $\lceil L/2 \rceil$ 为中位数（ $\lceil x \rceil$ 是向上取整， $\lceil 1.5 \rceil=2$ ）

思考一下，两个序列的中位数和最终结果有啥关系？

回答：最终的中位数在这两个中位数之间，所以我们应该舍弃较小中位数的前半部分和较大中位数的后半部分，直到最终取到我们要的结果。

拿一个例子来说明：

$1,2,5,6,7$ 和 $3,4,8,9,10$ 两个序列，这两个序列的中位数是 $\lceil 5/2 \rceil =3$ 也就是第 $3$ 个，就是 $5$ 和 $8$ ，我们分别舍弃 $1,2$ 和 $9,10$
然后我们还剩 $5,6,7$ 和 $3,4,8$ ，这次他们的中位数是 $6$ 和 $4$ 所以舍弃 $7$ 和 $3$
这次我们剩下 $5,6$ 和 $4,8$ 那中位数该如何选择呢？继续计算 $\lceil 2/2 \rceil =1$ 所以中位数是第 $1$ 个，也就是 $5$ 和 $4$ 很明显， $5,6$ 应该舍弃 $6$ ，那 $4,8$ 呢？应该舍弃哪个？没错就是中位数自己 $4$ 。最后我们对比两个数，取较小的即可。

所以，我们需要使用分治解决这个问题。
并且，在奇数的时候，只需要舍弃左侧的；在偶数长度的时候，较小的那个中位数不可能是最终中位数，就直接连同它一起舍弃

分治法 Divide and Conquer

标准的分治：“分而治之，全都要” 👐
标准的分治法核心口诀是 “分、治、合”。它的目标通常是处理所有数据，所以它不能随便丢弃任何东西
- 分 (Divide)： 把大问题切成两个或多个小问题。
- 治 (Conquer)： 递归地解决这些小问题。
- 合 (Combine)： 把小问题的答案拼起来，变成大问题的答案。
经典例子：归并排序 (Merge Sort)
想象你有一堆乱序的扑克牌 🃏。
- 分：把牌分成左半堆和右半堆。
- 治：把左边排好序，把右边也排好序（你都要做，不能把左边扔了）。
- 合：把两堆已经有序的牌，“拉链”式地合并成一整堆有序的牌。
- 结论： 这里没有“舍弃”，所有数据都被处理了。
这道题的分治：“减而治之，丢一半” ✂️
这通常被称为 减治法 (Decrease and Conquer)。这通常发生在查找类问题中。

当我们只需要找某一个特定的东西（比如“中位数”或“某个数字”）时，如果我们能确定目标绝对不在某一部分里，我们就可以大胆地把那部分“舍弃”掉。

经典例子：二分查找 (Binary Search) / 查字典 📖
想象你在字典里找 “Python” 这个词。
- 分：你翻开中间一页，是 “M”。
- 判断： “P” 在 “M” 后面。
- 舍弃： 你直接把前半本字典（A-M）扔掉不看，只在后半本里找。
- 结论： 这种策略之所以快，是因为每次都丢掉一半负担。

代码

#include <stdio.h>

int find_mid_number(const int a[], const int b[], int len) {
    int s1 = 0, e1 = len - 1;
    int s2 = 0, e2 = len - 1;
    int mid1, mid2;

    // 当只剩下一个元素时，跳出循环
    while (s1 != e1 || s2 != e2) {
        // 防溢出写法
        mid1 = s1 + (e1 - s1) / 2;
        mid2 = s2 + (e2 - s2) / 2;

        if (a[mid1] == b[mid2]) {
            return a[mid1]; // 相等即为中位数
        }

        // 计算偏移量：偶数长度需剔除中位数，奇数长度保留中位数
        int offset = (len % 2 == 0) ? 1 : 0;

        if (a[mid1] < b[mid2]) {
            // a的中位数小于b的中位数
            // 舍弃 a 的左半部分，舍弃 b 的右半部分
            s1 = mid1 + offset; 
            e2 = mid2;
        } else {
            // a的中位数大于b的中位数
            // 舍弃 a 的右半部分，舍弃 b 的左半部分
            s2 = mid2 + offset;
            e1 = mid1;
        }
        
        // 长度减半逻辑：(len + 1) / 2 同时适用于奇偶
        // 例如: len=4 -> 2, len=5 -> 3
        len = (len + 1) / 2;
    }

    // 最后剩下的两个元素取较小值（因为是求第N小的数，即下中位数）
    return (a[s1] < b[s2]) ? a[s1] : b[s2];
}

int main() {
    int a[] = {2, 5, 6, 9};
    int b[] = {3, 4, 6, 7};
    // 预期：合并后 [2,3,4,5,6,6,7,9]，长度8，下中位数是第4个元素(index 3) -> 5
    int mid = find_mid_number(a, b, 4);
    printf("Result: %d\n", mid);
    return 0;
}

这个代码属于难度较高的代码，无论是思路梳理还是代码编写难度都比较高
忌讳单次循环维护很多变量，比如 length start end mid 之类的，单次循环维护的变量越多越容易出错。