1.4　算法的效率

回到猜数字游戏，要猜1到100之间的随机整数，可以采用顺序查找算法，即从小到大依次猜，直到猜对为止。最坏的情况下，要猜100次才能猜对。

如果采用二分查找算法，每次猜中间的数值，依次将查找范围减半，则对于长度为100的数组，最坏的情况下，查找范围依次为100、50、25、12、6、3、1，因此最多7次（log₂100向上取整）就能猜对。

推广开来，如果数组大小为n，顺序查找最多需要猜n次，二分查找最多需要猜log₂n次。表1-1列出了不同数据规模下，两种查找算法的效率。数据规模越大，二分查找算法的效率优势越明显。

表1-1

算法的效率通常使用大O表示法来描述。比如顺序查找算法的时间复杂度记为O(n)，表示对规模为n的数据执行顺序查找算法的最长运行时间为n的常数倍。二分查找算法的效率可以记为O(log₂n)，表示对规模为n的数据执行二分查找算法的最长运行时间为n的对数函数。

还有一种比二分查找更快的查找算法，那就是哈希查找，也称为散列查找。哈希查找通过将关键字映射到哈希表中的索引位置来快速定位目标数据，其时间复杂度为O(1)。