猜谜游戏

让我们来玩一个小游戏来看看，为什么同一问题的不同算法会有截然不同的效率。假设计算机随机选择了一个从1到15的整数，您来猜，直到猜中这个数字为止。计算机会告诉您每次猜的是太高或太低：

在您找到了那个数字后，想一想刚才猜的时候是怎样决定下一个要猜的数的。

也许您先猜了1，然后是2，然后是3，然后是4，依此类推，直到您猜到了那个正确的数字。 我们将此方法称为线性搜索，因为您猜的数字一一递增就好像它们排成一行一样。这个方法确实可以找到那个正确的数字。但是最坏情况下需要猜多少次呢？ 如果计算机选择的是15，就需要猜15次。当然在最好情况下，计算机选择了1，而您第一次猜的就是1，这样一次就猜对了。平均需要猜多少次呢？如果计算机以同样的概率选择一个1到15之间的任何数字，那么平均而言，需要猜测8次。

但您是否可以做到比依序猜测1, 2, 3, 4, …, 更高效呢? 利用计算机会告诉您猜测是否太低，太高，或正确这一点，您可以一开始先猜8。如果计算机选择的数字小于8，而您也被告知猜的8太高，那就可以把8到15之间的所有数字从下次猜测中排除。如果计算机选择的数字大于8，那您就可以排除1到8之间的数字。不论怎样，您都可以排除一半的数字。 在下一次猜测中, 您又可以再排除剩余数字的一半。 以此往复，您就可以一直排除剩余数字的一半。

我们将这个排除一半的方法称为二分搜索。用这个方法，无论计算机选择了1到 15 之间的哪个数字，最多猜4次，您就一定能够找到这个数字。

在这里，尝试1到300的数字。 你应该不需要超过9个猜测。

这次你花了多少时间才找到这个数字？为什么你永远不需要超过9次猜测？(你能想到一个数学解释吗）？

让我们回到二分搜索， 我们将了解如何使用它来有效地搜索JavaScript数组中的元素。但首先, 让我们来看看一个更棘手的问题的算法。

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