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）说明你所设计算法的时间复杂度和空间复杂度。
A、和 B，试设计个在时间和空间两方向都尽可能高效的算法，找出两个序列A和B的中位数。要求∶ （1）给出算法的基本设计思想。 （2）根据设计思想，采用C或C++或 Java语言描述算法，关键之处给出注释。（3）说明你所设计算法的时间复杂度和空间复杂度。
【参考答案及解析】
（1）算法的基本设计思想如下。 分别求出序列A和B的中位数，设为a和b，求序列A和B的中位数过程如下∶ 1）若 a=b，则 a或b 即为所求中位数，算法结束。 2）若ab，则舍弃序列A中较小的一半，同时舍弃序列B中较大的一半，要求舍弃的长度相等; 3）若 a>b，则舍弃序列A中较大的一半，同时舍弃序列B中较小的一半，要求舍弃的长度相等; 在保留的两个升序序列中，重复过程 1）、2）、3），直到两个序列中只含一个元素时为止，较小者即为所求的中位数。 （2）算法的实现如下∶ int M Search (int A[],int B[],int n){ int sl=0,dl=n-1,ml,s2=1,d2=n-1,m2; //分别表示序列 A 和 B 的首位数、末位数和中位数 while(s1!=dl||s2!=d2){ ml=(sl+d1)/2; m2=(s2+d2)/2; if(A[m1] ==B[m2]) return A[ml]; //满足条件1） if（A[m1]if（（s1+d1）%2==0）{ //若元素个数为奇数 s1=ml; //舍弃 A中间点以前的部分且保留中间点 d2=m2; //舍弃 B中间点以后的部分且保留中间点 } else{ //元素个数为偶数 s1=ml+1; //舍弃A中间点及中间点以前部分 d2=m2; //舍弃B中间点以后部分且保留中间点 } } else{ //满足条件 3） if（（s1+d1）%2==0）{//若元素个数为奇数 d1=m1; //舍弃 A中间点以后的部分且保留中间点 s2=m2; //舍弃B中间点以前的部分且保留中间点力 } else{ //元素个数为偶数 d1=ml+1; //舍弃A中间点以后部分且保留中间点 s2=m2; //舍弃B中间点及中间点以前部分 } } } return A[s1]（3）算法的时间复杂度为0（log2n）），空间复杂度为0（1）。
正在整理中,欢迎在文下评论区提供答案解析,谢谢！
（1）算法的基本设计思想如下。 分别求出序列A和B的中位数，设为a和b，求序列A和B的中位数过程如下∶ 1）若 a=b，则 a或b 即为所求中位数，算法结束。 2）若ab，则舍弃序列A中较小的一半，同时舍弃序列B中较大的一半，要求舍弃的长度相等; 3）若 a>b，则舍弃序列A中较大的一半，同时舍弃序列B中较小的一半，要求舍弃的长度相等; 在保留的两个升序序列中，重复过程 1）、2）、3），直到两个序列中只含一个元素时为止，较小者即为所求的中位数。 （2）算法的实现如下∶ int M Search (int A[],int B[],int n){ int sl=0,dl=n-1,ml,s2=1,d2=n-1,m2; //分别表示序列 A 和 B 的首位数、末位数和中位数 while(s1!=dl||s2!=d2){ ml=(sl+d1)/2; m2=(s2+d2)/2; if(A[m1] ==B[m2]) return A[ml]; //满足条件1） if（A[m1]if（（s1+d1）%2==0）{ //若元素个数为奇数 s1=ml; //舍弃 A中间点以前的部分且保留中间点 d2=m2; //舍弃 B中间点以后的部分且保留中间点 } else{ //元素个数为偶数 s1=ml+1; //舍弃A中间点及中间点以前部分 d2=m2; //舍弃B中间点以后部分且保留中间点 } } else{ //满足条件 3） if（（s1+d1）%2==0）{//若元素个数为奇数 d1=m1; //舍弃 A中间点以后的部分且保留中间点 s2=m2; //舍弃B中间点以前的部分且保留中间点力 } else{ //元素个数为偶数 d1=ml+1; //舍弃A中间点以后部分且保留中间点 s2=m2; //舍弃B中间点及中间点以前部分 } } } return A[s1]（3）算法的时间复杂度为0（log2n）），空间复杂度为0（1）。
正在整理中,欢迎在文下评论区提供答案解析,谢谢！