一个长度为L（L≥1）的升序序列S 处在第éL/2ù个位置的数称为S的中位数。 例如：若序列S1=（11 13 15 17
一个长度为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条回复-
（1）算法的基本设计思想如下。 分别求出序列 A 和 B 的中位数，设为 a 和 b，求序列 A 和B 的中位数过程如下： 1）若 a=b，则 a 或 b 即为所求中位数，算法结束。 2）若 a 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] 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] } （3）算法的时间复杂度为 O(log 2 n)，空间复杂度为 O(1)。