## 問題描述 > 一個長度為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的中位數。 ## 算法思想 > 分別求兩個升序序列A，B中位數，設為a和b 1). 若a=b，則a或b即為所求中位數，算法結束； 2). 若a<b，則舍棄序列A中較小的一半，同時舍棄序列B中較大的一半，要求兩次舍棄的長度相等； 3). 若a>b，則設計序列A中較大的一半，同時設計序列B中較小的一半，要求兩次舍棄的長度相等； ## 算法描述 ~~~ int FindMid(int A[], int B[]) { int s1=0,d1=MaxSize-1,m1; int s2=0,d2=MaxSize-1,m2; while(s1!=d1||s2!=d2){ m1=(s1+d1)/2; m2=(s2+d2)/2; if(A[m1]<B[m2]){ if((s1+d1)%2==0){ s1=m1; d2=m2; }else{ s1=m1+1; d2=m2; } }else if(A[m1]>B[2]){ if((s2+d2)%2==0){ d1=m1; s2=m2; }else{ d1=m1; s2=m2+1; } }else{ return A[m1]; } } return A[s1]<B[s2]?A[s1]:B[s2]; } ~~~ 具體代碼見附件 ## 附件 ~~~ #include<stdio.h> #define MaxSize 5 int FindMid(int*, int*); int main(int argc,char* argv[]) { int A[MaxSize]={11,13,15,17,19}; int B[MaxSize]={2,4,6,8,20}; int Num; Num=FindMid(A,B); printf("The mid Num is %d\n",Num); return 0; } int FindMid(int A[], int B[]) { int s1=0,d1=MaxSize-1,m1; int s2=0,d2=MaxSize-1,m2; while(s1!=d1||s2!=d2){ m1=(s1+d1)/2; m2=(s2+d2)/2; if(A[m1]<B[m2]){ if((s1+d1)%2==0){ s1=m1; d2=m2; }else{ s1=m1+1; d2=m2; } }else if(A[m1]>B[2]){ if((s2+d2)%2==0){ d1=m1; s2=m2; }else{ d1=m1; s2=m2+1; } }else{ return A[m1]; } } return A[s1]<B[s2]?A[s1]:B[s2]; } ~~~