【题目】
42.(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)给出算法的基本设计思想：(5 分)
分别求两个升序序列A、B 的中位数，设为a 和b。若a=b，则a 或b 即为所求的中位数;否则，舍弃a、b 中较小者所在序列之较小一半，同时舍弃较大者所在序列之较大一半，要求两次舍弃的元素个数相同。在保留的两个升序序列中，重复上述过程，直到两个序列中均只含一个元素时为止，则较小者即为所求的中位数。
(2)算法实现：(8 分)
int M _ Search(int A[ ],int B[ ],int n){
int start1, end1, mid1, start2, end2, mid2 ;
start1 =0;end1 =n-1 ;
start2 = 0 ; end2 = n- 1 ;
while(start1 ! = end1 || start2 ! = end2)
{ mid1 = (start1 +end1 )/2 ;
mid2 = ( start2 +end2 )/2 ;
if(A[mid1 ] = =B[mid2]) return A[mid1 ] ;
if( A [ mid1 ]
{//分别考虑奇数和偶数，保持两个子数组元素个数相等
if((start1+end1)%2==0){//若元素为奇数个
start1=mid1; //舍弃A 中间点以前的部分且保留中间点
end2=mid2; //舍弃B 中间点以后的部分且保留中间点
}
else{ //若元素为偶数个
start1=mid1+1;//舍弃A 的前半部分
end2=mid2; //舍弃B 的后半部分
}
}
else{
if((start1+end1)%2=：0){//若元素为奇数个
end1=mid1; //舍弃A 中间点以后的部分且保留中间点
start2=mid2; //舍弃B 中间点以前的部分且保留中间点
}
else{//若元素为偶数个
end1=mid1; //舍弃A 的后半部分
start2=mid2+1;//舍弃B 的前半部分
}
}
}
return A[start1]
}
(3)上述所给算法的时间、空间复杂度分别是0(log2n)和0(1)。(2 分)