二分查找法：如何高效使用数组

相较于之前的线性搜索方法，二分查找法采用逐步访问的方式寻找所需的数据。当数据量庞大时，这种方法显得效率低下。例如，如果数据有1000条记录，那么采用线性搜索法平均需要查找500次，但若采用本节讨论的二分查找法，最多不会超过10次（2^10=1024）。在使用二分查找法之前应先对数据进行排序。在一个已排序的序列中，首先与序列中间值比较，如果待查数据比中间值大，则待查数据必定在中间值的后面；反之则在前面。因此，二分查找法每次可以将搜索范围减半，这对于大量数据时可以提高查询效率。例如，在上例中，必须先对数据进行排序，则二分查找的算法如下：