medi.cpp

对于给定的n个元素的数组X[0:n-1]和Y[0:n-1],试设计一个O(logn)时间算法,计算X和Y的中位数.

//////////////////////////////////////////////////////////////////
//     设两个长度为n的数列分别为x[0:n-1]和y[0:n-1],             //
//     分别找出这两个数列的中位数x[i]和y[j],二者进行比较,       //
//     根据比较结果可以在每个数列中减少一半的搜索范围,然后再    //
//     分别取两个子数列的中位数再比较,再减少搜索范围,继续下     //
//     去直到找到最后结果。(分治法)                             //
//////////////////////////////////////////////////////////////////
#include <stdio.h>
#include <fstream.h>
int FIND_MEDIAN(int* a, int* b, int len)  //分治法查找中位数。
{
	int *m = a;
	int *n = b;
	while (1)
		{
		if (len<=1)
			return m[len-1]<n[len-1]?m[len-1]:n[len-1]; //各剩下一个数时，直接比较，把最小的输出。
		int mp = (len - 1)/2;       //数组的中间的下标。                 
		int ma = m[mp];
		int mb = n[mp];
		if (ma == mb)               //中位数相等时，输出其中的一个。 
			return ma;
		else if (ma<mb)             //数组a的中位数小于数组b的中位数时，
				{                   //去掉数组a中小于其中位数的数，
			    m = m + len/2;      //同时去掉数组b中大于其中位数的数。
				len = (len+1)/2;    
				}
			else
				{                   //数组a的中位数大于数组b的中位数时，    
				n = n + len/2;      //去掉数组a中大于其中位数的数，
				len = (len+1)/2;    //同时去掉数组b中小于其中位数的数。
				}
		}
}
void main()
{ 
	int median;
	int n;
	ifstream input("input.txt");   
	ofstream output("output.txt");
	input>>n;                      //从文件读取数组个数
	if (n>0)
		{
		int* X=new int[n];         //申请堆空间给数组
		int* Y=new int[n];
		for(int i=0;i<n;i++)
			input>>X[i];           //从文件读取数组X的值
		for(int j=0;j<n;j++)
			input>>Y[j];           //从文件读取数组Y的值
		median=FIND_MEDIAN(X,Y,n); 
		delete[] X;                //释放堆空间
		delete[] Y;
		output<<median;            //向文件输出结果(中位数).
		}
}