e.cpp

二分搜索是运用分治策略的典型例子。二分搜索方法充分利用了元素间的次序关系

#include<iostream.h>
 int BinarySearch(int a[],int s,int n)
 {
	 int left=0;int right=n-1;
	 while(left<=right)
	 {
		 int middle=(left+right)/2;
		 if(s==a[middle])
			 return middle;
		 if(s>a[middle]) 
			 left=middle+1;
		 else
			 right=middle-1;
	 }
	 return -1;
 }
 void main()
{
 int s;
 int n=6;
 cout<<"请输入维数n：" <<endl;
 cin>>n;
 int a[]={23,56,62,97,100,463};
 cout<<"请输入数组："<<endl;
 for(int l=0;l<n;l++)
 {
     cin>>a[l];
 }
 cout<<"请输入所要查询的数："<<endl;
 cin>>s;
 if(BinarySearch(a,s,n)==-1)
	 cout<<"不在数组中。"<<endl;
 else
	 cout<<"在数组中的第"<<BinarySearch(a,s,n)+1<<"位"<<endl; 
}