AC112-找出两个等长升序序列的中位数LeetCode 4. Median of Two Sorted Arrays¶

一个长度为 L 的升序序列 S，处在第 ⌈L/2⌉（向上取整）个位置的数称为 S 的中位数。例如，S₁ = (11, 13, 15, 17, 19)，S₁ 的中位数为 15。两个序列的中位数是指将它们的所有元素合并成一个升序序列后，该合并序列的中位数。例如，若 S₂ = (2, 4, 6, 8, 20)，则 S₁ 和 S₂ 的合并序列为 (2, 4, 6, 8, 11, 13, 15, 17, 19, 20)，其中位数为 11。

现在有两个等长的升序序列 A 和 B，试设计一个在时间和空间都尽可能高效的算法，找出两个序列 A 和 B 的中位数。（2011 年统考题）

二分查找

代码实现¶

C
// 函数 Find：找出两个等长升序序列的中位数
int Find(Sqlist A, Sqlist B) {
    Sqlist C;              // 创建一个新的顺序表用于存储合并后的序列
    int i = 0, j = 0, k = 0;  // 初始化三个指针：i指向A，j指向B，k指向C

    // 合并两个升序序列到C中
    while (i < A.length && j < B.length) {
        // 比较A和B当前指针指向的元素，将较小的元素放入C中
        if (A.data[i] < B.data[j]) {
            C.data[k++] = A.data[i++];  // 将A中的元素放入C，并移动相应指针
        } else {
            C.data[k++] = B.data[j++];  // 将B中的元素放入C，并移动相应指针
        }
    }

    // 将A中剩余的元素复制到C中（如果有的话）
    while (i < A.length) {
        C.data[k++] = A.data[i++];
    }

    // 将B中剩余的元素复制到C中（如果有的话）
    while (j < B.length) {
        C.data[k++] = B.data[j++];
    }

    // 返回合并后序列的中位数
    // 由于题目中定义中位数为第L/2(向上取整)个位置的数
    // 在0索引的数组中，第L/2个位置对应索引为L/2-1
    return C.data[k/2 - 1];
}

代码逻辑解析¶

1. 数据结构定义¶

C
typedef struct {
    int data[100];  // 存储升序序列的数组
    int length;     // 序列的实际长度
} Sqlist;

2. 算法步骤详解¶

步骤1：初始化 - 创建结果顺序表C用于存储合并后的序列 - 初始化三个指针：i指向序列A的开始，j指向序列B的开始，k指向结果序列C的开始

步骤2：合并两个有序序列 - 使用归并排序的思想，比较两个序列当前指针指向的元素 - 将较小的元素放入结果序列C中，并移动相应的指针 - 重复此过程直到其中一个序列遍历完成

步骤3：处理剩余元素 - 将未遍历完的序列中的剩余元素全部复制到结果序列C中

步骤4：计算中位数位置 - 根据题目定义：长度为L的序列，中位数位于第⌈L/2⌉个位置 - 在0索引的数组中，第⌈L/2⌉个位置对应索引为⌈L/2⌉-1 - 由于k表示合并后序列的总长度，所以中位数位置为k/2-1

示例说明¶

假设： - A = [11, 13, 15, 17, 19]（长度为5） - B = [2, 4, 6, 8, 20]（长度为5）

合并过程：

Text Only
1 2 3	`A: [11, 13, 15, 17, 19] B: [2, 4, 6, 8, 20] C: [2, 4, 6, 8, 11, 13, 15, 17, 19, 20]`

合并后序列C长度为10，中位数位置为第⌈10/2⌉=5个位置，即索引4，值为11。

时间复杂度分析¶

详细分析：¶

合并过程：while(i < A.length && j < B.length)
每次循环至少移动一个指针
最多执行 min(A.length, B.length) 次比较
时间复杂度：O(min(m,n))，其中m和n分别为两个序列的长度
处理剩余元素：
while(i < A.length)：最多执行(A.length - i)次
while(j < B.length)：最多执行(B.length - j)次
时间复杂度：O(m+n)
总体时间复杂度：O(m+n)
由于题目中说明两个序列等长，设长度均为n，则时间复杂度为O(n)

空间复杂度分析¶

详细分析：¶

额外空间使用：
创建了新的顺序表C用于存储合并后的序列
C的长度等于两个输入序列长度之和
如果两个序列长度均为n，则C需要2n个存储空间
空间复杂度：O(m+n)
由于题目中说明两个序列等长，设长度均为n，则空间复杂度为O(n)

✅ 最优解法：二分查找法（带详细注释）¶

C++
int findMedian(vector<int>& A, vector<int>& B) {
    int n = A.size();  // 两个序列长度均为 n
    int low = 0, high = n;  // 在 A 中的切割位置范围 [0, n]
                            // cut = 0 表示全部元素在右半部分
                            // cut = n 表示全部元素在左半部分

    // 二分搜索在 A 中的切割点
    while (low <= high) {
        // 在 A 中选择切割位置 cut1：表示 A 的左半部分有 cut1 个元素
        int cut1 = low + (high - low) / 2;

        // 在 B 中的切割位置 cut2：由于总左半部分需要有 n 个元素（因为中位数是第 n 个）
        // 所以 B 的左半部分有 n - cut1 个元素
        int cut2 = n - cut1;

        // 获取四个边界值，用于判断是否满足中位数条件

        // A 左半部分的最大值（如果 cut1 == 0，说明 A 没有左半部分）
        int left1 = (cut1 == 0) ? INT_MIN : A[cut1 - 1];

        // A 右半部分的最小值（如果 cut1 == n，说明 A 没有右半部分）
        int right1 = (cut1 == n) ? INT_MAX : A[cut1];

        // B 左半部分的最大值
        int left2 = (cut2 == 0) ? INT_MIN : B[cut2 - 1];

        // B 右半部分的最小值
        int right2 = (cut2 == n) ? INT_MAX : B[cut2];

        // 判断是否找到了正确的分割：
        // 要使合并序列的左半部分（共 n 个元素） <= 右半部分
        // 需要满足：
        //   A 左最大 <= B 右最小   （A 的左半部分不会跑到右边去）
        //   B 左最大 <= A 右最小   （B 的左半部分不会跑到右边去）
        if (left1 <= right2 && left2 <= right1) {
            // 此时左半部分的最大值就是中位数（因为总共有 2n 个元素，中位数是第 n 个）
            // 左半部分的最大值 = max(A 左最大, B 左最大)
            return max(left1, left2);
        }
        // 如果 A 的左半部分太大（left1 > right2），说明 cut1 太靠右，需要左移
        else if (left1 > right2) {
            high = cut1 - 1;
        }
        // 如果 B 的左半部分太大（left2 > right1），说明 cut1 太靠左，需要右移
        else {
            low = cut1 + 1;
        }
    }

    // 理论上一定会在循环内返回，这里防止编译警告
    return -1;
}

🧠 算法核心思想解析¶

1. 目标¶

找出两个等长升序序列合并后的中位数（第 n 小的元素）。

2. 关键洞察¶

合并后序列长度为 2n，中位数是第 n 个元素（从1开始计数）。
我们不需要真正合并数组，只需要将两个数组各切一刀，使得：
左半部分总共 n 个元素
右半部分总共 n 个元素
左半部分所有元素 ≤ 右半部分所有元素

3. 切割（Partition）思想¶

在 A 中切在位置 cut1：A[0...cut1-1] 属于左半部分
在 B 中切在位置 cut2：B[0...cut2-1] 属于左半部分
要求：cut1 + cut2 = n ⇒ cut2 = n - cut1

4. 合法切割的条件¶

一个切割是“合法”的（即能形成中位数），当且仅当：

Text Only
1	`max(A 左, B 左) ≤ min(A 右, B 右)`

即： - A[cut1-1] ≤ B[cut2] （A 左 ≤ B 右） - B[cut2-1] ≤ A[cut1] （B 左 ≤ A 右）

5. 二分策略¶

在 A 的 [0, n] 范围内二分搜索 cut1
根据上述条件调整搜索区间

⏱️ 时间复杂度分析¶

每次循环：O(1) 操作（比较、赋值）
循环次数：对 cut1 进行二分搜索，搜索空间为 [0, n]，共 n+1 个位置
时间复杂度：O(log n)

这是理论最优的，因为任何比较排序模型下，查找第 k 小元素的下界是 Ω(log n)

💾 空间复杂度分析¶

额外空间：只使用了常数个变量（low, high, cut1, cut2, left1, right1 等）
没有创建新数组或递归栈
空间复杂度：O(1)

✅ 正确性保证¶

初始状态：low=0, high=n，覆盖所有可能的切割位置
循环不变量：合法的切割点始终在 [low, high] 范围内
终止条件：找到满足 left1 ≤ right2 && left2 ≤ right1 的切割点
边界处理：使用 INT_MIN 和 INT_MAX 避免数组越界

🎯 举例说明¶

设 A = [11, 13, 15, 17, 19]，B = [2, 4, 6, 8, 20]，n = 5

我们希望左半部分有 5 个元素。

cut1	cut2	A 左	A 右	B 左	B 右	条件	中位数
2	3	[11,13]	[15,...]	[2,4,6]	[8,...]	13≤8? ❌	—
3	2	[11,13,15]	[17,...]	[2,4]	[6,...]	15≤6? ❌	—
4	1	[11,13,15,17]	[19]	[2]	[4,...]	17≤4? ❌	—
5	0	[11,13,15,17,19]	[]	[]	[2,4,6,8,20]	19≤2? ❌	—
0	5	[]	[11,...]	[2,4,6,8,20]	[]	20≤11? ❌	—
1	4	[11]	[13,...]	[2,4,6,8]	[20]	11≤20 ✔️, 8≤13 ✔️	max(11,8)=11 ✅

最终返回 11，正确。

📌 总结¶

项目	说明
算法思想	二分查找 + 分割（Partition）
核心技巧	将中位数问题转化为“合法分割”问题
时间复杂度	O(log n) ⭐ 最优
空间复杂度	O(1) ⭐ 最优
适用场景	两个有序数组找中位数（可推广到不等长）
扩展性	可推广到找第 k 小元素问题

> 💡 此算法是 LeetCode 4. Median of Two Sorted Arrays 的简化版（等长情形），但思想完全一致，是算法设计中的经典范例。¶

延伸知识点¶

1. 归并排序思想¶

本算法使用了归并排序中合并两个有序数组的核心思想
归并排序的时间复杂度为O(n log n)，但合并两个已排序数组的时间复杂度为O(n)

2. 中位数的不同定义¶

奇数长度序列：中位数是正中间的元素
偶数长度序列：通常取中间两个元素的平均值
本题特殊定义：取第⌈L/2⌉个位置的元素

3. 相关算法问题¶

寻找两个有序数组的第k小元素
寻找两个有序数组的中位数（不等长情况）
多个有序数组的合并问题

4. 实际应用场景¶

数据库查询优化
统计分析中的分位数计算
分布式系统中的数据合并