一个长度为 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) 说明你所设计算法的时间复杂度和空间复杂度。
[tag_link]
(1) 求两个序列 A 和 B 的中位数最简单的办法就是将两个升序序列进行归并排序，然后求其中位数。这种解法虽可求解，但在时间和空间两方面都不大符合高效的要求，但也能获得部分分值。根据题目分析，分别求两个升序序列 A 和 B 的中位数，设为 a 和 b。① 若a=b，则a或b即为所求的中位数。原因：容易验证，如果将两个序列归并排序，则最终序列中，排在子序列 b 前边的元素为先前两个序列中排在 a 和 b 前边的元素；排在子序列 ab 后边的元素为先前两个序列中排在 a 和 b后边的元素。所以子序列 ab 一定位于最终序列的中间，又因为 a=b，显然 a 就是中位数。②否则（假设a<b)，中位数只能出现 (a,b) 范围内。原因：同样可以用归并排序后的序列来验证，归并排序后必然有形如⋯a⋯b⋯的序列出现，中位数必出现在 (a,b) 之间。因此可以做如下处理：舍弃 a 所在序列 A 的较小一半，同时舍弃 b 所在序列 B 的较大一半。在保留两个升序序列中求出新的中位数 a 和 b，重复上述过程，直到两个序列中只含一个元素时为止，则较小者即为所求的中位数。每次总的元素个数变为原来的一半。算法的基本设计思想如下。分别求出序列 A 和 B 的中位数，设为 a 和 b，求序列 A 和 B 的中位数过程如下：① 若a=b，则 a 或 b 即为所求中位数，算法结束。② 若a<b，则舍弃序列 A 中较小的一半，同时舍弃序列 B 中较大的一半，要求舍弃的长度相等。③ 若a>b，则舍弃序列 A 中较大的一半，同时舍弃序列 B 中较小的一半，要求舍弃的长度相等。在保留的两个升序序列中，重复过程①、②、③，直到两个序列中只含一个元素时为止，较小者即为所求的中位数。
2）算法实现
int M_Search(int A[], int B[], int n) {
int s1 = 0, d1 = n - 1, m1, s2 = 1, d2 = n - 1, m2;
// 分别表示序列 A 和 B 的首位、末位和中位数
while (s1 != d1 || s2 != d2) {
m1 = (s1 + d1) / 2;
m2 = (s2 + d2) / 2;
if (A[m1] == B[m2])
return A[m1]; // 满足条件 1
if (A[m1] < B[m2]) { // 满足条件 2
if ((s1 + d1) % 2 == 0) {
// 若元素个数为奇数
s1 = m1; // 舍弃 A 中间点以后的部分，且保留中间点
d2 = m2; // 舍弃 B 中间点以前的部分，且保留中间点
} else {
// 元素个数为偶数
s1 = m1 + 1; // 舍弃 A 中间点及中间点以后的部分
d2 = m2; // 舍弃 B 中间点以前部分，且保留中间点
}
} else { // 满足条件 3
if ((s1 + d1) % 2 == 0) {
// 若元素个数为奇数
d1 = m1; // 舍弃 A 中间点以前的部分，且保留中间点
s2 = m2; // 舍弃 B 中间点以后的部分，且保留中间点
} else {
// 元素个数为偶数
d1 = m1 + 1; // 舍弃 A 中间点及中间点以前部分
s2 = m2; // 舍弃 B 中间点以后的部分，且保留中间点
}
}
}
return A[s1] < B[s2] ? A[s1] : B[s2];
}
3）时间复杂度 O(n)，空间复杂度 O(
1)。