本以为自己会写二分查找,不过就是取中间值和要找的对象进行比较大小,再根据比较的结果,选择左边还是右边。最终找到要找的东西。但是正如Jon Bentley所说

90%以上的程序员无法正确无误的写出二分查找代码。 ——Jon Bentley

我就是那90%中的一员。每次写二分总有一种魔幻的感觉。一会儿死循环,一会儿与答案相差一。。。。。简直是要了我的老命了。总之就是找不到任何头绪。这次我Google了一下在维基百科上找到了关于二分查找的资料,讲的非常的详细。我在这里做一下总结。

二分查找一般是在有序的序列中通过每次进行对半分的操作进行数据的检索。因为每次都为对半分操作,所以时间复杂度为$O(\log_2 n)$效率非常高。

二分查找的实现并不复杂但是坑实在多,让我来列举几个我知道的几个需要注意的地方。

  1. (a + b) / 2的精度丢失问题,比如(1 + 2) / 2 = 1。
  2. 体会r = mid和r = mid - 1之间的区别。
  3. 还有答案应该取什么值得问题,mid,l还是r。

在这里我们考虑一个问题就是二分查找的区间问题:

当区间为[a, b]的时候区间应该分为[a, mid - 1]和[mid + 1, b]循环条件为while(l <= r)

而当区间为[a, b)的时候区间应该分为[a, mid)和[mid + 1, b)循环条件为while(l < r)

请注意其中括号的区别,还有在(l + r) / 2时如果l和r接近2^31 - 1那么会很容易溢出所以在不知道范围的时候最好用l + ((r - l) >> 1)。

还有一种二分方法,在题目我们很多时候并不知道具体二分查找要找到的值,往往是要求一个最大值,或者是最小值在这样的情况下,如果我们还按照原来的二分方法,验证mid可以之后就让l = mid + 1,很可能答案就是mid,mid + 1就不行了,但是现在的区间已经变为了[mid + 1, r]或者是[mid + 1, r),这样怎么都不会得到正确答案,但是如果我们把l的更新改成l = mid,这样的话又会导致死循环,所以解决办法就是在每一次l = mid + 1时设立一个变量ans = mid,这样就可以使ans总是最后一个验证成功的答案,最后输出ans即可。如果要求最小值,正好和这个是相反的,就不说了。

当然在不同的题目中要根据不同的题目做出不同的灵活变动。

参考:

维基百科-Binary search algorithm

程序员编程艺术:面试和算法心得

那谁的技术博客