求序列的中位数

// 一个长度为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)，直到
// 两个序列中均只含一个元素时为止，较小者即为所求的中位数。

int M_Search(int A[], int B[], int n) 
{
    int start1 = 0, end1 = n - 1, m1, start2 = 0, end2 = n - 1, m2;
    //分别表示序列A和B的首位数、末位数和中位数
 
    while (start1 != end1 || start2 != end2)
    {
        m1 = (start1 + end1) / 2;
        m2 = (start2 + end2) / 2;
        if (A[m1] == B[m2])
            return A[m1];   //满足条件 1)
 
        if (A[m1]<B[m2]) // 满足条件 2)
        {  
            if ((start1 + end1) % 2 == 0)  //若元素个数为奇数
            {  
                start1 = m1;  //舍弃A中间点以前的部分且保留中间点
                end2 = m2;  //舍弃B中间点以后的部分且保留中间点
            }
            else                //元素个数为偶数
            { 
                start1 = m1 + 1;  //舍弃A中间点及中间点以前部分
                end2 = m2;  //舍弃B中间点以后部分且保留中间点
            }
        }
        else
        {  //满足条件3)
            if ((start2 + end2) % 2 == 0)   //若元素个数为奇数
            { 
                end1 = m1;    //舍弃A中间点以后的部分且保留中间点
                start2 = m2;    //舍弃B中间点以前的部分且保留中间点
            }
            else     //元素个数为偶数
            {  
                end1 = m1;    //舍弃A中间点以后部分且保留中间点
                start2 = m2 + 1;    //舍弃B中间点及中间点以前部分
            }
        }
    }
    return  A[start1]<B[start2] ? A[start1] : B[start2];
}