二分查找（Binary Search）算法，也叫折半查找算法，是一种针对有序数据集合的查找算法。

    1无处不在的二分思想

        二分查找是一种非常简单易懂的快速查找算法，生活中到处可见，比如我们现在来做一个猜字游戏，随机写一个0-99之间的数字，来猜猜这个数字是多少。假设要猜的数字是23，那么二分查找的过程如下：

        我们可以看到，7次就猜出来了。按照这个思想，即便是0-999的数字，最多也只要10次就能猜中。

        再来一个例子，我们假设有10个订单，金额分别是：8,11,19,23,27,33,45,55,67,98。我们想要查询这个名单中是否有19这个金额的订单，还是利用二分思想，过程如下图，其中low和high表示待查找区间的下标，mid表示待查找区间的中间元素下标。

        总结一下，二分查找针对的是一个有序的数据集合，查找思想有点类似分治思想，每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，知道找到要查找的元素，或者区间被缩小为0。

    2O(logn)惊人的查找速度

        二分查找非常高效，高效到什么程度呢？

        下面分析一下它的时间复杂度。

        最坏情况下，直到查找区间被缩小为空才停止，被查找区间的大小变化如下图：

        当n/2^k=1时，k的值就是总共缩小的次数。而每次缩小操作只涉及两个数据的大小比较，所以经过了k次区间缩小操作后时间复杂度就是O(k)。由n/2^k=1可得k=log2n，所以时间复杂度就是O(logn)。

        对数时间复杂度O(logn)是一种极其高效的时间复杂度，有时候甚至比时间复杂度是常量级O(1)的算法还要高效，为什么这么说呢？

        因为 logn 是一个非常“恐怖”的数量级，即便 n 非常非常大，对应的 logn 也很小。比如 n 等于 2 的 32次方，这个数很大，大约是 42 亿。也就是说，如果我们在42 亿个数据中用二分查找一个数据，最多需要比较 32 次。

        而我们之前有说过，用大O标记法表示时间复杂度的时候，会省略掉常数、系数和低阶，对于常量级时间复杂度的算法来说，O(1)可能表示的是一个非常大的常量值，比如O(1000)、O(10000)。因此常量级时间复杂度的算法有时候可能还没有O(logn)的算法执行效率高。

        反过来，对数对应的就是指数。指数时间复杂度的算法在大规模数据面前是无效的。

    3二分查找的递归与非递归实现

        最简单的情况就是有序数组中不存在重复元素，下面用Java代码实现一个最简单的二分查找算法。

        我的代码：

        运行结果：

        几个需要注意的点：

        1.循环退出条件是low<=high而不是low<high。

        2.mid取值一般写法为mid=(low+high)/2，但是如果low和high比较大的话，两者之和就有可能会溢出，改进的方法是将mid的计算方式写成low+(high-low)/2。更进一步，如果要将性能优化到极致的话，我们可以将这里的除以2操作转换成位运算low+((high-low)>>1)。因为相比除法运算来说，计算机处理位运算要快得多。

        注意这里哦，我第一次就犯了这个错呜呜：

        3.注意low和high的更新应该写为low=mid+1,high=mid-1，不能直接写成low=mid或者high=mid，否则可能会发生死循环。

        二分查找除了用循环来实现，也可以用递归来实现，代码如下：

        结果同上。

        戳这里查看源代码。

    4二分查找应用场景的局限性

        首先，二分查找依赖的是顺序表结构，简单点说就是数组。

        二分查找不能依赖其他数据结构，比如链表。因为二分查找算法是按照下标随机访问元素，数组按照下标随机访问元素的时间复杂度是O(1)，而链表随机访问的时间复杂度是O(n)。所以如果数据使用链表存储，二分查找的时间复杂度就会变得很高。

        因此，二分查找只能用在数据是通过顺序表来存储的数据结构上。

        其次，二分查找针对的是有序数据。

        二分查找的数据必须是有序的，如果没有序，需要先排序，而维持有序的时间成本比较高。

        再次，数据量太小不适合二分查找。

        如果数据量很小，完全没有必要二分查找，顺序遍历就OK了，因为两种方法时间都差不多，只有数据量大的时候，二分查找的优势才会比较明显。

        但是有一个例外，就是如果数据之间的比较操作非常耗时，那不管数据量大小，都推荐用二分查找。比如，如果数组中存储的都是长度超过300的字符串，如此长的两个字符串之间对比大小，就会非常耗时。

        最后，数据量太大也不适合二分查找。

        二分查找的底层需要依赖数组这种数据结构，数组为了支持随机访问的特性，要求内存空间连续，对内存要求比较苛刻。所以太大的数据用数组存储就比较吃力，也就不能用二分查找了。

    5内容小结

        今天我们学习了一种针对有序数据的高效查找算法，二分查找，它的时间复杂度是O(logn)。二分查找的核心思想理解起来非常简单，有点类似分治思想，即每次都通过跟区间中的中间元素对比，将待查找的区间缩小为一般，直到找到要查找的元素，或者区间缩小为0。实现二分查找的代码需要注意三个容易出错的地方：循环退出条件、mid的取值、low和high的更新。

        二分查找虽然性能很棒棒，但是应用场景比较有限，比层必须依赖数组，并且还要求数据是有序的。对于较小规模的数据查找，我们直接使用顺序遍历就OK了，二分查找的优势并不明显。二分查找更适合处理静态数据，也就是没有频繁的数据插入、删除操作。

    6思考题

        1.如何编程实现“求一个数的平方根”？要求精确到小数点后6位。

        2.如果数据是用链表存储的，使用二分查找的时间复杂度是多少呢？

        后面有空了我再用代码实现查找平方根！