两序列的中位数算法

  #include<stdio.h>
int M_Search(int A[],int B[],int n)
{
	//分别表示序列A和B的首位数、末位数和中位数的下标
	int s1=0,d1=n-1,m1,s2=0,d2=n-1,m2;
	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中间点级中间点以前部分
			}
		}
	}
	return A[s1]<B[s2]?A[s1]:B[s2];
}
int main()
{
	int A[]={1,2,3,4,5,6};
	int B[]={6,7,8,9,10,11};
	int n=6;
	int middle=M_Search(A,B,n);
	printf("中位数=%d",middle);
	return 0;
}