数据结构
2011-42
一个长度为L（L≥1）的升序序列S，处在第[L/2]个位置的数称为S的中位数。例如，若序列S1=(11,13,15,17,19)，则S1的中位数是15，两个序列的中位数是含它们所有元素的升序序列的中位数。例如，若S2=(2,4,6,8,20)，则S1和S2的中位数是11。现在有两个等长升序序列A和B，试设计一个在时间和空间两方面都尽可能高效的算法，找出两个序列A和B的中位数。
要求：
（1）给出算法的基本设计思想。
（2）根据设计思想，采用C、C++或Java语言描述算法，关键之处给出注释。
（3）说明你所设计算法的时间复杂度和空间复杂度。
答案
（1）算法的基本设计思想
分别取当前两个子序列 A' 和 B' 的中位数 a 和 b。
- 若 a == b，则 a（或 b）即为所求中位数。
- 若 a < b，则中位数不可能出现在 A' 的前半部分（含 a）和 B' 的后半部分（含 b）中。因此舍弃 A' 的前半部分和 B' 的后半部分，且舍弃长度相等。
- 若 a > b，则舍弃 A' 的后半部分和 B' 的前半部分，且舍弃长度相等。
重复上述过程，直到两个子序列都只剩一个元素，较小者即为所求中位数。
（2）算法的 C++ 实现
int M_Search(int A[], int B[], int n) {
// 分别本轮搜索中A、B的起始位置和结束位置
int start1 = 0, end1 = n - 1, start2 = 0, end2 = n - 1;
// 分别本轮搜索中A、B的中位数
int m1, m2;
// 直到一个数组被遍历完
while (start1 != end1 || start2 != end2) {
m1 = (start1 + end1) / 2;
m2 = (start2 + end2) / 2;
// 满足情况(1)
if (A[m1] == B[m2])
return A[m1];
// 满足情况(2)
if (A[m1] < B[m2]) {
// 考虑奇偶为保证子数组元素个数相同
if ((start1 + end1) % 2 == 0) {
start1 = m1;
end2 = m2;
} else {
start1 = m1 + 1;
end2 = m2;
}
}
// 满足情况(3)
if (A[m1] > B[m2]) {
// 考虑奇偶为保证子数组元素个数相同
if ((start1 + end1) % 2 == 0) {
end1 = m1;
start2 = m2;
} else {
end1 = m1;
start2 = m2 + 1;
}
}
}
// 返回较小的
return A[start1] < B[start2] ? A[start1] : B[start2];
}（3）时间复杂度和空间复杂度
- 时间复杂度：每次迭代将搜索范围减半，因此时间复杂度为 O(log n)。
- 空间复杂度：只使用了常数个辅助变量，因此空间复杂度为 O(1)。