（15 分）一个长度为 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 的中位数过程如下： 
1）若 a=b，则 a 或 b 即为所求中位数，算法结束。 
2）若 a<b，则舍弃序列 A 中较小的一半，同时舍弃序列B 中较大的一半,要求舍弃的长 度相等； 
3）若 a>b，则舍弃序列 A 中较大的一半，同时舍弃序列 B 中较小的一半，要求舍弃的 
长度相等； 
在保留的两个升序序列中，重复过程 1）、2）、3），直到两个序列中只含一个元素时为止，较小者即为所求的中位数。 
（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(log₂n)，空间复杂度为 O(1)。