[C算法]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$ ）

我们最容易想到的就是归并排序找中位数，但归并排序会占用 $O(n)$ 的空间，这个题目是寻找中位数，所以我们只用模拟归并，用一个数来存储找到的结果就好。

既然是两个序列，所以就是长度为偶数的序列里找中位数，也就是第 $L$ 个，也就是下标为 $L-1$ 的那个数。

代码（模拟归并）

int merge_find_mid_number(int A[], int B[], int L) {
    int i = 0, j = 0, count = 0;
    int res = -1;

    while (count < L) {
        if (A[i] <= B[j]) {
            res = A[i++];
        } else {
            res = B[j++];
        }
        count++;
    }
    return res;
}

这个函数很简单，用 while 保证了向后移动 $L-1$ 次，也就是找到下标为 $L-1$ 的数。每次移动都要更新现在的结果。
对比的时候，要取较小值，让对应的下标往后移。

复杂度分析（模拟归并）

时间复杂度： $O(n)$
空间复杂度： $O(1)$

题目再分析

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

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

拿一个例子来说明：

$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(int A[], int B[], int n) {
    if (n <= 0) return -1;
    int A_s = 0, A_e = n - 1;
    int B_s = 0, B_e = n - 1;

    // 当每个序列都只查找到剩最后一个的时候退出
    while (A_s < A_e) {
        // 中位数是向上取整的
        int A_mid = (A_s + A_e) / 2;
        int B_mid = (B_s + B_e) / 2;

        if (A[A_mid] == B[B_mid])
            return A[A_mid];

        // 维护一个现在操作的序列长度，比修改 n 更直观
        int current_len = A_e - A_s + 1;
        // 偏移量，分奇偶，偶数长度需剔除中位数，奇数长度保留中位数
        int offset = current_len % 2 == 0 ? 1 : 0;

        // 中位数对比
        if (A[A_mid] <= B[B_mid]) {
            A_s = A_mid + offset;
            B_e = B_mid;
        } else {
            A_e = A_mid;
            B_s = B_mid + offset;
        }
    }

    // 只剩两个数了，返回较小值
    return A[A_s] < B[B_s] ? A[A_s] : B[B_s];
}

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 之类的，单次循环维护的变量越多，越容易出错。

复杂度分析（分治法）

时间复杂度： $O(logn)$
空间复杂度： $O(1)$