如何使用二分查找提升数组的检索效率？
首先，如果数据是无序存储的话，无论是数组还是链表，想要查找一个指定元素是否存在，在缺乏数据分布信息的情况下，我们只能从头到尾遍历一遍，才能知道其是否存在。这样的检索效率就是 O(n)。当然，如果数据集不大的话，其实直接遍历就可以了。但如果数据集规模较大的话，我们就需要考虑更高效的检索方式。
对于规模较大的数据集，我们往往是先将它通过排序算法转为有序的数据集，然后通过一些检索算法，比如 二分查找算法 来完成高效的检索。
二分查找也叫折半查找，它的思路很直观，就是将有序数组二分为左右两个部分，通过只在半边进行查找来提升检索效率。那二分查找具体是怎么实现的呢？让我们一起来看看具体的实现步骤。
我们首先会从中间的元素查起，这就会有三种查询结果。
第一种，是中间元素的值等于我们要查询的值。也就是，查到了，那直接返回即可。
如果中间元素的值小于我们想查询的值，那接下来该怎么查呢？这就是第二种情况了。数组是有序的，所以我们以中间元素为分隔，左半边的数组元素一定都小于中间元素，也就是小于我们想查询的值。因此，我们想查询的值只可能存在于右半边的数组中。
对于右半边的数组，我们还是可以继续使用二分查找的思路，再从它的中间查起，重复上面的过程。这样不停地「二分」下去，每次的检索空间都能减少一半，整体的平均查询效率就是 O(log n)，远远小于遍历整个数组的代价 O(n)。
同理，对于第三种情况，如果中间元素的值大于我们想查询的值，那么我们就只在左边的数组元素查找即可。
由此可见，合理地组织数据的存储可以提高检索效率。检索的核心思路，其实就是通过合理组织数据，尽可能地快速减少查询范围。在专栏后面的章节中，我们会看到更多的检索算法和技术，其实它们的本质都是通过灵活应用各种数据结构的特点来组织数据，从而达到快速减少查询范围的目的。
