2.7.2　二分查找算法

二分查找算法是搜索算法中用得最多、最简单易用、效率较好的搜索算法。但它有一个前提条件，即查找所用的数组必须是有序的数组。也就是说，在使用二分查找算法前，必须对数组进行排序，而且在每次更改、插入、删除后都要进行排序以保证数组的有序状态。

二分查找算法的步骤如下。

1）将数组分为三块，即前半部分区域、中间位元素、后半部分区域。

2）将要查找的值与数组的中间位元素进行比较，若小于中间位，则在前半部分区域查找，若大于中间位，则在后半部分区域查找，如果等于中间位，则直接返回。

3）继续在选择的查找范围中查找，跳入步骤1），依次进行递归操作，将当前选择的范围继续拆分成前半部分、后半部分和中间位元素这三部分，直到范围缩到最小，如果还是没有找到匹配的元素，则说明元素并不在数组里。

二分查找算法的平均时间复杂度为O(lgN)，它是一个效率比较高的查找算法，这也是它常被用到的原因，不过前提是数组为有序的，这对于一些情况下的搜索来说，门槛可能会比较高，它们可能需要不停地插入或删除元素，这种情况下，可以使用二分查找算法先查找到插入的位置，再执行插入操作，但是插入操作本身就是O(N)的平均时间复杂度，导致查找速度无论多快都还是抵不过插入带来的消耗，删除也是同样的道理，数组的复制操作已经成为算法中的瓶颈。我们来看看其他搜索算法是怎么做的。