C语言求两个升序序列的中位数

这里涉及到数据结构中顺序表的实现、删除、插入、查找等知识，请查看：数据结构 -> 线性表

问题描述：

一个长度为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) 说明你所设计算法的时间复杂度和空间复杂度。

该题为2011年研究生考试计算机联考真题。

问题解答：

(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, ml, 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]<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((s2+d2)%2==0){  //若元素个数为奇数
                d1=m1;    //舍弃A中间点以后的部分且保留中间点
                s2-m2;    //舍弃B中间点以前的部分且保留中间点
            }else {  //元素个数为偶数
                d1=m1;    //舍弃A中间点以后部分且保留中间点
                s2=m2 + 1;    //舍弃B中间点及中间点以前部分
            }
        }
    }
    rerurn A[s1]<B[s2]?A[s1]:B[s2];
}

(3)算法的时间复杂度为O(log2n)，空间复杂度为O(1)。