Explanation and Application of Binary Search Algorithm

二分查找有着查找速度快，平均性能好等优点，但仅当列表是有序的时候，二分查找才管用。面试中比较常考，这篇文章来讲解一下二分查找算法。

我们先从一个场景开始了解吧

有一天，小明心血来潮去图书馆借了 N 本书，结果出图书馆的时候，警报响了，于是门卫大爷把小明拦下，要检查一下哪本书没有登记出借。小明正准备把每一本书在报警器下过一下，以找出引发警报的书，但是大爷露出不屑的眼神：你连二分查找都不会吗？于是大爷把书分成两堆，让第一堆过一下报警器，报警器响；于是再把这堆书分成两堆…… 最终，检测了 logN 次之后，大爷成功的找到了那本引起警报的书，露出了得意和嘲讽的笑容。于是小明背着剩下的书走了，心想：大爷果然还是我大爷！

是不是觉得二分查找很简单？！其实思想是很简单，但是有不少细节需要注意。正如 Knuth 大佬（发明 KMP 算法的那位）所说：

Although the basic idea of binary search is comparatively straightforward, the details can be surprisingly tricky…

大致意思就是：思路很简单，细节是魔鬼。

接下来我就带大家来分析需要注意的细节，以及二分查找的巧妙运用。

点击阅读更多看全文。