binary.cpp

利用二分搜索技术实现数组元素的查找,实现了算法设计中的分治策略

/*分治法的典型代表--二分查找搜索技术
  编程日期：2009.05.16
  作者：小威^^
*/
#include<iostream>
using namespace std;

template <class Type>
int BinarySearch(Type a[],const Type &x,int n)
{
	int left=0,right=n-1;
	while(left<=right)
	{
		int mid=(left+right)/2;
		if(a[mid]==x) 
			return mid;
		else if(a[mid]<x)
			left=mid;
		else
			right=mid;
	}
	return -1;
}
void main()
{
	int n,x;
	int result;
	cout<<"请输入有序的数组的大小n："<<endl;
	cin>>n;
	int *a=new int[n];
	cout<<"请输入一个有序的数组："<<endl;
	for(int i=0;i<n;i++)
		cin>>a[i];
	cout<<"请输入要查找的数的大小？"<<endl;
	cin>>x;
	result=BinarySearch(a,x,n);
	cout<<"你要查找的元素的在数组中的位置是："<<result<<endl;

}