test_hw9_1.cpp

清华文件 考研用. Distribution of this memo is unlimite

#include<iostream.h>

void main()
{
	int n;                      //数组A和B中所含的元素个数
	cout<<"Please input the number of n (elements in both A and B):"<<endl;
	cin>>n;

	int *A;                     //数组A
	int *B;                     //数组B
	A=new int[n]; 
	B=new int[n];

	cout<<"Please input the elements in A:"<<endl;
	for(int i=0;i<n;i++)
	{
		cin>>A[i];
	}

	cout<<"Please input the elements in B:"<<endl;
	for(int j=0;j<n;j++)
	{
		cin>>B[j];
	}

	int k=0;
	int m=0;
	int B_left=0;               //B中寻找范围的左边界
	int B_right=n-1;            //B中寻找范围的右边界
	int mid;                    //中位数
	while(1)
	{
		m=(B_left+B_right)/2;
		k=n-2-m;

		//A的前k+1个元素和B的前m+1个元素合起来恰为A与B合成序列的前n个元素
		if(A[k+1]>=B[m]&&B[m+1]>=A[k])
		{
			//A[k]和B[m]中值较大的元素为中位数
			if(A[k]>=B[m])
			{
				mid=A[k];
			}
			else
			{
				mid=B[m];
			}
			break;
		}
		//A中最后一个元素(A[n-1])仍小于B中第一个元素(B[0])，说明B中的所有元素均大于A中的元素，则中位数为A中最后一个（最大的）元素
		else if(m==0)
		{
			mid=A[k+1];
			break;
		}
		//B中最后一个元素(B[n-1])仍小于A中第一个元素(A[0])，说明A中的所有元素均大于B中的元素，则中位数为B中最后一个（最大的）元素
		else if(m==n-2)
		{
			mid=B[m+1];
			break;
		}
		//继续寻找
		else
		{
			//B中元素取多了，则在m左边的区域里寻找合适的m值
			if(A[k+1]<B[m])
			{
				B_right=m;
			}
			//B中元素取少了，则在m右边的区域里寻找合适的m值
			else
			{
				B_left=m;
			}
		}
	}

	cout<<"The middle number is "<<mid<<endl;

}