二分查找

 

如果查找表中的数据元素按关键字有序（假设递增有序），则在查找时，可不必逐个顺序比较，而采用跳跃的方式——先与“中间位置”的数据元素关键字比较，若相等，则查找成功；若给定值大于 “中间位置”的关键字，则在查找表的后半部继续进行二分查找，否则在前半部进行二分查找。

 

代码如下：

#include <iostream>
using namespace std;
const int N=1e6+5;
//在数组a(n个元素)中查找x; 
int a[N+5],s;
int bi_search(int a[],int n,int x)
{
	int l=0,r=n-1;
	s=0;
	while(l<=r){
		s++;
		//取中间位置 
		int m=(l+r)/2;
		if(x==a[m])//找到返回下标 
			return m;
		if(x<a[m])//在左半区间继续查找
			r=m-1;
		else	//在右半区间继续查找 
			l=m+1;		
	}
	return -1; 
}
int main()
{
	
	for(int i=0;i<N;i++)
		a[i]=i+1;
	int x;
	while(cin>>x){
		int t=bi_search(a,N,x);
		cout<<s<<endl;
		if(t==-1)
			cout<<"Not Found!"<<endl;
		else
			cout<<t<<endl;	 
	}	
}