你好创造者

【2011年计算机联考真题】
  一个长度为L（L≥1）的升序序列S，处在第2/L个位置的数称为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）说明你所设计算法的时间复杂度和空间复杂度。

想必大家想到是O(n)的算法复杂度和O(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 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]<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((s1+d1)%2==0) { //若元素个数为奇数     
                d1=m1;  //舍弃A中间点以后的部分且保留中间点     
                s2=m2;  //舍弃B中间点以前的部分且保留中间点    
            } 
            else{  //元素个数为偶数     
                d1=m1+1;  //舍弃A中间点以后部分且保留中间点     
                s2=m2;    //舍弃B中间点及中间点以前部分    
            } 
        } 
    } 
    return A[s1]<B[s2]? A[s1]:B[s2]; 
}

转载需经作者允许并注明出处(http://hiunique.com/data-structures/8.html)
来自:你好创造者