erfenjiansuo.cpp

利用分治法实现二分检索,分治法的基本思想是分而治之

#include<iostream.h>
int Binsrch(int,int,int,int a[]);
void Com(int a[]);
int main()
{
	int i,m,n;
	int a[10];
	char x;
	cout<<"请输入10个元素:";
	for(i=0;i<10;i++)
		cin>>a[i];
	Com(a);
	cout<<"对该10个元素排序后为:";
	for(int j=0;j<10;j++)
		cout<<a[j]<<" ";
	cout<<endl;
	do
	{
	cout<<"请输入要查找的数:";
	cin>>m;
	n=Binsrch(0,9,m,a);
	if(n!=-1)
	cout<<"该元素在排序数组后的位置:"<<n<<endl;
	else cout<<"该元素不在该数组中!"<<endl;
	cout<<"你是否继续查找(y/n)?";
	cin>>x;
	}while(x=='y');
	return 0;
}
void Com(int a[])
{
	int i,j,m1,m2,t;
	for(i=0;i<10;i++)
	{
		m1=a[i];
		for(j=i+1;j<10;j++)
		{
			m2=a[j];
			if(a[i]>a[j])
			{
				t=a[i];
				a[i]=a[j];
				a[j]=t;
			}
		}
}
}
int Binsrch(int low,int high,int find,int a[])
{
	int mid;
	static int count1=0;
	static int count2=0;
	count1++;
	mid=(low+high)/2;
	if(find==a[mid])
	{
		mid++;
		cout<<"按二分检索你要查找的次数是:"<<count1-count2<<endl;
		count2=count1;
		return mid;
	}
	else if(find>a[mid]&&high>mid)
	{   
		mid++;
		Binsrch(mid,high,find,a);
	}
	else if(find<a[mid]&&low<mid)
	{
		mid--;
		Binsrch(low,mid,find,a);
	}
	else
	{

		cout<<"按二分检索你要查找的次数是:"<<count1-count2<<endl;
		count2=count1;
		return -1;
	}
}