Not Only Algorithm,不仅仅是算法,关注数学、算法、数据结构、程序员笔试面试以及一切涉及计算机编程之美的内容 。。
你的位置:NoAlGo博客 » 其它算法 » ,

二分查找

二分查找是一种经典的算法,是每个程序员的入门内容之一,但是根据《编程珠玑》上面介绍,90%的程序员写的二分查找的程序中有bug,并且他并不认为没有bug的代码就是正确的。
可见二分查找是比较考验程序员的编码基本功的。那么如何查找数组中一个元素是否存在并且如何找出其第一次或最后一次出现的位置呢?本文接下来将对这个问题进行仔细分析并提供相应的代码。

一 查找是否存在

对于一个已经排好序的数组,二分查找能够在logn的时间内找出一个元素在里面是否出现过,如果出现,返回其出现的位置,否则返回-1。

二分查找的思路很简单,每次考察中间的元素,如果刚好是要找的,则直接返回,否则比较中间元素与目标元素的大小。如果中间元素比较大,说明目标元素在中间元素的左边;如果中间元素比较小,说明目标元素在中间元素的右边。然后再在缩小的范围内按这种方法继续查找,直到找到目标元素或者数组变为空为止。

二分查找有一些细节需要额外注意。

  1. 递归还是非递归。递归会有额外的函数调用的开销,而且非递归算法并不会太复杂,这里我们使用的是非递归的算法。
  2. 区间开闭。我们用st和ed表示算法当前处理的数组的最小下标和最大下标,对于n个元素的数组,算法可以使用st=0,ed=n进行处理,这时处理的数组实际上是一个左闭右开的区间[st,ed)。这里我们使用的是闭区间的方法,即st=0,ed=n-1。使用了闭区间[st,ed]之后,数组只有一个元素时会有st==ed,所以我们循环的条件是st<=ed。
  3. 中间下标计算。中间的下标mid可以直接用(st+ed)/2进行计算,但这样有比较多弊端,如除法性能较低,加法可能溢出等。我们采用的方法是st+((ed-st)>>1),使用位移运算替代除法,并且避免溢出问题。另外,以前这篇文章提到的(st&ed)|((st^ed)>>1)也能计算平均值。
  4. 下标修改。这个比较直接,如果目标元素在左边部分时,我们让ed=mid-1,如果在右边部分时,让st=mid+1。因为中间mid所在元素已经分析过了,所以在下次查找时不用再包含这个元素。这样修改之后新的区间肯定不会跟原区间一样,算法不会进入死循环。
  5. 返回值。如果在循环内找到的话,我们直接返回结果。如果循环终止了,说明目标元素不存在,我们直接返回-1。

综合以上几点,可以得到的二分查找的代码如下:

//在数组a的[st,ed]中查找tar
int binarySearch0(int a[], int st, int ed, int tar)
{
	while (st <= ed)
	{
		int mid = st + ((ed - st) >> 1);
		if (tar == a[mid]) return mid;
		else if (tar > a[mid]) st = mid + 1;
		else ed = mid - 1;
	}
	return -1;
}

我们用几个简单的例子测试这个程序,首先先定义几个待检测的数组如下:

int a1[] = {1};
int a2[] = {1, 1};
int a3[] = {1, 2};
int a4[] = {1, 1, 2};
int a5[] = {0, 1, 1};
int a6[] = {1, 1, 1};

我们在主函数中进行测试,测试在以上数组中查找1的结果。为了后面修改的方便,使用一个宏定义函数名。

int main()
{
#define binarySearch binarySearch0
	cout << binarySearch(a1, 0, 0, 1) << endl; //0
	cout << binarySearch(a2, 0, 1, 1) << endl; //0
	cout << binarySearch(a3, 0, 1, 1) << endl; //0
	cout << binarySearch(a4, 0, 2, 1) << endl; //1
	cout << binarySearch(a5, 0, 2, 1) << endl; //1
	cout << binarySearch(a6, 0, 2, 1) << endl; //1
}

二 查找第一次出现

以上的程序可以查找出一个元素是否存在,但如果该元素出现多次时,其返回的位置是不确定的。如果要保证返回第一次出现的位置呢?

显然,我们可以在上面程序的结果之后,逐个往左边遍历,直到第一次出现的位置为止。但这样不够高效(如10000个0查找0),这里不予以考虑。

在数组a的当前区间[st,ed]中,因为查找的是tar的第一次出现,如果a[mid]>=tar,我们可以知道mid+1及其右边的所有元素都不可能是答案,因为他们要么大于tar,要么等于tar但不是第一次出现,所以我们可以直接让ed=mid。而如果a[mid]<tar呢,这时mid及其左边的元素不可能是答案,因为他们都是小于tar的,所以我们让st=mid+1。这样,每次分析都能够把待测区间的长度缩短为一半。

但是这样做之后的循环条件不能是st<=ed了。因为当只有一个元素的时候,st==ed,mid=st,这时如果选择了ed=mid的分支,则st和ed都保持不变,程序就会陷入死循环。考虑到只有一个元素的数组我们可以直接比较,所有循环条件直接改为st<ed。

循环终止时我们需要判断当前的st的元素是否为目标元素,如果是就返回下标st,否则返回-1。

//在数组a的[st,ed]中查找tar第一次出现的位置
int binarySearch1(int a[], int st, int ed, int tar)
{
	while (st < ed)
	{
		int mid = st + ((ed - st) >> 1);
		if (a[mid] >= tar) ed = mid;
		else st = mid + 1;
	}
	return a[st] == tar ? st : -1;
}

还是用以上a1到a6的6个测试数组,修改main中的宏定义,简单测试以上函数的结果。

int main()
{
#define binarySearch binarySearch1
	cout << binarySearch(a1, 0, 0, 1) << endl; //0
	cout << binarySearch(a2, 0, 1, 1) << endl; //0
	cout << binarySearch(a3, 0, 1, 1) << endl; //0
	cout << binarySearch(a4, 0, 2, 1) << endl; //0
	cout << binarySearch(a5, 0, 2, 1) << endl; //1
	cout << binarySearch(a6, 0, 2, 1) << endl; //0
}

三 查找最后一次出现

相应地,怎么查找数组中某个元素的最后一次出现的位置呢?同样地,不考虑查找任意出现再遍历到最后出现的做法。

我们还是考虑a[mid],因为要查找的是最后一次出现,如果a[mid]<=tar,我们可以知道mid-1及其左边的所有元素都不可能是答案,因为他们要么小于tar,要么等于tar但不是最后一次出现,所以我们让st=mid。而如果a[mid]>tar呢,这时mid及其右边的元素都不是答案,因为他们都大于tar,所以我们让ed=mid-1。同样地,每次分析都能够把待测区间的长度缩短为一半。

但是这时使用st<ed作为循环条件又有问题了。因为当只有两个元素的时候,ed=st+1,mid=st+((ed-st)>>1)=st,这时如果选择了st=mid的分治,则st和ed都保持不变,程序就会陷入死循环。这时应该怎么处理呢?问题的根本是在于连续的两个数取平均时会得到第一个数,然后才可能让st保持不变。我们可以稍微修改平均值的计算方法,mid=st+((ed-st+1)>>1),这时连续两个数的平均会得到后一个数,于是避免了上述问题。

程序代码为:

//在数组a的[st,ed]中查找tar最后一次出现的位置
int binarySearch2(int a[], int st, int ed, int tar)
{
	while (st < ed)
	{
		int mid = st + ((ed - st + 1) >> 1);
		if (a[mid] <= tar) st = mid;
		else ed = mid - 1;
	}
	return a[st] == tar ? st : -1;
}

同样进行测试:

int main()
{
#define binarySearch binarySearch2
	cout << binarySearch(a1, 0, 0, 1) << endl; //0
	cout << binarySearch(a2, 0, 1, 1) << endl; //1
	cout << binarySearch(a3, 0, 1, 1) << endl; //0
	cout << binarySearch(a4, 0, 2, 1) << endl; //1
	cout << binarySearch(a5, 0, 2, 1) << endl; //2
	cout << binarySearch(a6, 0, 2, 1) << endl; //2
}

四 总结扩展

二分查找一个容易出错的地方是导致死循环,程序中需要特别注意循环条件、中间下标计算、区间下标修改及修改的条件等几方面的细节。

这里分析并给出了三种二分查找的算法思路和一种C++代码的实现方式,但是算法的实现是灵活的,如果使用了其他的实现方法同样要注意这几个方面的问题。

另外,第二、三部分实现的是查找给定元素的第一次和最后一次出现位置,我们可以很容易地对其进行扩展,使其能够查找满足某个条件的元素的第一次出现或者最后一次出现的位置,具体只要根据实际情况修改if的判断条件和最后return返回时的判断条件即可。

上一篇: 下一篇:
  1. 第二部分,在数组a的[st,ed]中查找tar第一次出现的位置的判断条件是不是写错了?是st

      • 是st小于ed,两次留言小于号后面的文字都没了。。。你的代码里面写的是小于等于

        • 这个留言该不会是把小于号当成html标签了吧。。那个应该是没等于的,已经改过来了,谢谢啦

我的博客

NoAlGo头像编程这件小事牵扯到太多的知识,很容易知其然而不知其所以然,但真正了不起的程序员对自己程序的每一个字节都了如指掌,要立足基础理论,努力提升自我的专业修养。

站内搜索

最新评论