第1章第1节练习题10 查找中位数

问题描写叙述

一个长度为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

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]

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]

}

详细代码见附件

附件

#include

#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]

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]

}

参考链接