【ACM教程】3.3二分查找

第三节 二分查找

  这次我们要学习的，就是著名的高效的，并且应用非常广泛的二分查找算法，简称二分法（Binary Search）。二分查找的时间复杂度为O(lgn)，是优化程序的常用方法之一。在我们使用的java教科书中，经常会见到作者举的一个例子——猜数字。这个程序就是让你去猜测一个给定范围内的数字，当然，我们可以暴力一点，把所有可能的结果都掏出来试一试——枚举。但是真正在写程序的时候，这样效率可能会非常低，这个时候我们就需要使用二分法来去做这个游戏。

  我们可以这样去做：选择这个区间中间的数，大了，就把它当做新的区间的起点，继续做；小了就往左去找区间，以此类推，这就是我们在数学上学习过的二分法，那么，怎么能够在程序中实现呢？代码如下：

int bSearch(int a[],int b,int low,int high)
{
	int mid;
	if(low>high) return -1;
	mid=(low+high)/2;
	if(b==a[mid]) return mid;
	if(b<a[mid]) return bSearch(a,b,low,mid-1);
	else return bSearch(a,b,mid+1,high);
}

  我们看代码中的函数使用了四个参数，其中需要注意的是，第一个参数不仅仅是一个普通的数组，而是一个经过排序的序列，所以应该对需要查找的数组进行排序再进行二分查找。需要注意的是，我们应当注意对相同数据的处理，就是说如果我们的序列中会出现相同的数据，它应当返回哪一个下标。

  这个函数的功能是查找一个数在数组中是否存在，如果存在返回它的下标；如果不存在，则返回-1。在C++的STL中，给我们提供了类似的函数binary_search()，它的功能是判断一个数是否在给定序列中存在，返回值类型为布尔型。它的三个参数分别为：

binary_search(起始地址，终止地址，查找值);

  遗憾的是，上面的函数只能告诉我们这个值是否存在，并不能知道它的确切位置，这个时候，我们可以使用这两个函数：lower_bound()和upper_bound()。这两个函数是用来算出要查元素的上界和下界的，意思是说，对于序列中出现相同的元素的情况，这两个函数是可以解决的。但是，需要注意的是：

返回值的类型是地址,不是下标；
如果元素出现一次，lower_bounder()返回这个元素的地址，upper_bounder()返回它后面一个元素的地址；
如果元素出现多次，lower_bounder()返回第一个元素的地址，upper_bounder()返回最后一个元素的后面一的元素的地址。

  返回值是地址怎么办，我们也可以想办法投机取巧。我们知道，一个数组的名同时是一个数组第一个元素的地址，那么拿得到的地址减去首地址，就刚好是这个元素在数组中的下标了：

lower_bounder(a,a+100,shu)-a

  除此之外，二分法还有非递归的写法，大家可以了解一下：

int bSearch(int a[],int b,int n)
{
	int low,high,mid;
	low=0;high=n-1;
	while(low<=high) {
		mid=(low+high)/2;
		if(a[mid]==b) return mid;
		if(a[mid]<b) low=mid+1;
		else high=mid-1;
	}
	return -1;
}