本文共 1130 字，大约阅读时间需要 3 分钟。

题目：一个长度为L(L≥1)的升序序列S，处在第[L／2]个位置的数称为S的中位数。例如列S1=(11，13，15，17，19)，则S1中的中位数是15。两个序列的中位数是含它们所有元素的升序序列的中位数。例如，若92=(2，4，6，8，20)，则．S1和S2的中位数是11。现有两个等长升序序列A和B，试设计一个在时间和空间两方面都尽可能高效的算法，找出两个序列A和B的中位数。

要求： (1)给出算法的基本设计思想。

(2)根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。

(3)说明你所设计算法的时间复杂度和空间复杂度。

答：

（1）算法思想：将A和B用二路归并合并排序成C，找C的中位数。

根据题目，序列S为奇数，5个元素，下标（0+4）/2=2，刚好第三个元素下标是2。，S的元素个数为偶数10，（0+9）/2 = 4 ，刚好取第5个元素。A、B等长，合并之后元素个数一定是偶数。

（2）C代码：

int Mid_Search(int A[], int B[], int n){	int C[2n]; //要求分配最多存储2n个整数的存储空间，C指向这块空间	int i, j, k;	for(i=0, j=0, k=0; i

解析：

1. n为数组长度，A、B长度相等，A、B最大下标n-1，合并后C的最大下标2n-1
2. for循环初始化i，j为0。入口条件是i、j同时小于n，即遍历完一个数组就退出循环。另一个数组的剩余部分由下面的while循环执行。
3. 将A、B的元素比较，将较小的那个写到数组C中。
4. C[k] = A[i++]；相当于执行C[k] = A[i]； i++；for循环会再将k自增1，表示下一次较小的元素存放在C的位置。
5. 一个数组遍历完成后，退出for循环。另一个数组的所有元素都比当前C中的元素大，再依次存放数组C中。
6. 最后返回C的中位数，即为所求的中位数。

（3）该算法时间复杂度为O(n)，空间复杂度为O(n)。

以上不是最佳算法，下面最优算法太难想。

时间复杂度为O(log2n),空间复杂度为O(1)。

int M_Search(int A[],int B[],int n){    int s1=0,d1=n-1,m1,s2=0,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]

转载地址：http://veeii.baihongyu.com/