C++ 算法——二分查找

如果要你在一个升序序列中查找一个值的位置，你是否还会傻乎乎的用下面这个 $\mathcal{O}(n)$ 的代码暴力查找，如果是，我告诉你，其实根本不用这么做。

int find(int a[],int n,int k) {
	for(int i=0;i<n;++i) if(a[i]==k) return i;
}

猜数字这个游戏大家都玩过吧，这里介绍以下规则：

1. 一名玩家在一个范围内想出一个数。
2. 这名玩家告诉其他玩家他所想的范围。
3. 其他玩家在这个范围内猜数，若：
   • 猜中了：该玩家获胜
   • 没猜中：根据该玩家猜的数缩小范围，然后接着进行操作 2。对于缩小范围，设初始范围为 $l\sim y$，要猜的数为 $n$，猜的数位 $n$，若：
     • $m<n$，将范围缩小至 $m\sim r$。
     • $m>n$，将范围缩小至 $l\sim m$。

显然，想要最快猜到该数，就需要采用折半的方法去猜，每次都猜这个范围的中间数。二分查找也是一样，对于每一次查找，都判断中间的数与要找的数的大小关系，然后采取对应的操作。

需要注意的是，二分查找需要保证序列是升序的。

这里放个代码：

//循环版
int find(int a[],int n,int k) {
	int l=0,r=n-1;
	while(l<=r) {
		int mid=(l+r)/2;
		if(a[mid]>k) r=mid-1;
		else if(a[mid]<k) l=mid+1;
		else if(a[mid]==k) return mid;
	}
	return -1;
}
//递归版
int find(int a[],int n,int k,int l,int r) {
	if(l>r) return -1;
	int mid=(l+r)/2;
	if(a[mid]>k) return find(a,n,k,l,mid-1);
	else if(a[mid]<k) return find(a,n,k,mid+1,r);
	else if(a[mid]==k) return mid;
}

练习题：洛谷 link