二分搜索的运行时间

我们知道线性搜索对于长度为$n$‍的数组可能会需要$n$‍次搜索。 您可能已经有一个直观的想法，二分搜索比线性搜索具有更少的猜测次数。您甚至可能已经意识到，随着数组长度的增加，线性搜索和二分搜索的最坏情况猜测数之间的差异变得更加明显。让我们看看如何分析二分搜索的最大猜测数。

关键思路是, 当二分搜索进行不成功的猜测时, 数组中的可能范围将缩小至少一半。如果可能范围有32个元素, 那么一个不正确的猜测最多可以把它缩小到16。二分搜索每一次不成功的猜测都会把可能范围减半。

如果我们从长度为8的数组开始, 则不正确的猜测会将可能的范围的缩小到 4， 然后是 2，然后是1。一旦可能的范围只包含一个元素， 就不会再进一步猜测了；这个只包含一个元素的部分的猜测结果是正确的或不正确的，然后我们就完成了。因此, 使用长度为8的数组, 二分搜索最多需要四个猜测。

你认为16个元素的数组会怎么样？如果第一个猜测会消除至少8个元素，那么最多剩下8个元素，你就可以得到如图所示。因此，对于16个元素，我们最多需要5个猜测。

到现在, 你可能已经看到了某种模式。每次我们把数组的大小增加一倍, 我们最多需要多一个猜测。假设我们最多需要对长度为 $n$‍ 的数组进行$m$‍次猜测。然后, 对于长度为$2n$‍的数组, 第一次猜测把需要猜测的范围缩小到 $n$‍ 大小, 最多 $m$‍ 次猜测就会结束, 给我们一个最多 $m+1$‍次猜测。

让我们来看看数组长度为 $n$‍的一般情况。在最坏的情况下, 我们可以将猜测的次数描述为 "我们可以反复减半的次数，从 $n$‍开始，反复减半，直到我们得到 1，最后再加上1。" 但这写起来很繁琐。

幸运的是, 有一个数学函数, 它的作用是与我们反复减半相同， 从$n$‍开始, 直到我们得到值 1: 以2为底的$n$‍的对数。通常写作${\log }_{2}n$‍，但你也可能会看到它在计算机科学相关书籍中写为$\lg n$‍。(想回顾对数吗？点击此处了解更多。

下表显示了各种 $n$‍的值与以2为底的对数的对比:

我们可以把这个同样的表看成图形:

把较小的n值放大：

对数函数增长非常缓慢。对数是指数的反转，指数函数增长非常快，因此，如果${\log }_{2}n=x$‍，则$n=2^x$‍。例如， 因为${\log }_{2}128=7$‍， 反之则有$2^7=128$‍。

二分搜索算法运行时间，在$n$‍正好是2的幂时很容易地计算。如果$n$‍ 是128，二分搜索将需要最多8 (${\log }_{2}128+1$‍) 次猜测。

如果$n$‍ 不是2的幂怎么办？此时，我们可以寻找一个值，最接近但不超过该值的2的幂。对于长度为1000的数组，最接近但不超过1000的2的幂是512，即 $2^9$‍。因此，我们可以估计 ${\log }_{2}1000$‍ 为大于9且小于10数，或者利用计算器知道这个值是9.97，加上1得到10.97。遇到有小数的情况，直接舍去小数来得到实际猜测次数。因此，对于长度为1000的数组，二分搜索最多必须猜测10次。

Tycho-2星的目录下有 2,539,913 颗星星， 最接近的但不超过这个数的2的幂是 $2^{21}$‍ (即 2,097,152)，所以我们最多需要22次猜测。比线性搜索 好多了！

$n$‍ vs ${\log }_{2}n$‍的比较如下:

在下一个教程中, 我们将看到计算机科学家如何描述线性搜索和二分搜索的运行时间, 使用一种符号表示法来提取运行时间中最重要的部分并丢弃不太重要的部分。

本内容是 达特茅斯计算机科学 教授 Thomas Cormen 和 Devin Balkcom，与可汗学院的计算课程团队合作完成。内容获得许可 CC-BY-NC-SA。