If you're seeing this message, it means we're having trouble loading external resources on our website.

如果你被网页过滤器挡住,请确保域名*.kastatic.org*.kasandbox.org 没有被阻止.

主要内容

实现数组的二分搜索

让我们看看如何理解有序数组上的二分搜索。是的, JavaScript(以及其他许多编程语言) 已经提供了方法,用于确定给定元素是否在数组中,以及 ,如果是则返回其位置 。但我们希望自己实现它, 以了解如何实现这些方法。下面是前25个质数的 JavaScript 数组, 按顺序:
var primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97];
假设我们想知道数字67是否为素数。如果67在数组中, 即是素数。
我们可能还想知道有多少质数小于67。如果我们在数组中找到数字67的位置, 我们可以用它来计算存在多少个比它小的质数。
元素在数组中的位置称为其索引。数组索引从0开始, 向上计数。如果元素位于索引 0, 则它是数组中的第一个元素。如果一个元素在索引 3, 则有3个元素在数组位于它的前方。
看看下面的例子, 我们可以从左到右依次读取质数数组, 直到我们找到数字 67 (在粉红色的框中), 并看到它的数组索引为18。按这样的顺序查找数字是一个 线性搜索
一旦我们找到了67在索引18的位置上,我们就能确定67是个质数。我们也同时能很快知道数组中有18个元素小于67,即18个质数小于67。
你看到这个用了多少步骤吗? 二分搜索可能更有效。因为这个数组 primes 包括25个数字,数组索引范围从0到24。使用我们前面讲到的伪代码, 一开始,我们让 min = 0 , max = 24。二分搜索的第一次猜测将从索引12开始 (即 (0 + 24) / 2)。 primes[12] 等于67吗? 不,primes[12]是41。
我们正在寻找的索引比12高还是低? 因为数组中的元素是升序排列,且41 < 67,则67应该在索引12的右边。换句话说,我们正在猜测的值的索引比12要大。 我们用12 + 1即13来更新 min,保持max为24不变。
下一个要猜测的索引是什么?13和24的平均值是18.5, 我们将其四舍五入到18, 因为数组中的索引必须是整数。我们发现 primes[18]是67。
二分搜索算法在这里停止, 因为它已经找到了答案。它只需要两次猜测, 而不是线性搜索所用的19个猜测。您可以在下面的动画中重现所有步骤:

伪代码

我们只是描述了二分搜索算法, 逐步分析了一个例子。这是一种方法, 但用人类的语言解释算法在质量上可能会有所不同。它可以太短,也可以太长,最重要的是,它经常不精确,算法需要精确。我们可以转而以JavaScript 或 Python 等编程语言向您显示二分搜索,但程序包含大量详细信息——由于编程语言的要求, 或者因为程序必须处理异常, 这些异常包括错误的数据、用户的错误或系统故障----这些异常处理逻辑可能会使人们难以从仅仅研究代码中理解底层算法。这就是为什么我们更喜欢用一种叫做伪代码的方法来描述算法, 它将英语与您在编程语言中看到特性混合在一起。
这里是二分搜索的伪代码,已经修改成了从数组中查找。输入参数是数组,我们称之为arraynarray的元素个数,target是需要查找的数字。输出是targetarray 中的索引:
  1. min = 0(猜测值范围的最小界限), max = n-1(猜测值范围的最大界限).
  2. 计算 maxmin的均值作为guess (猜测的目标值的索引),向下取整。
  3. 如果 array[guess] 等于 target (目标值),则停止。你找到了! 返回guess
  4. 如果 guess 太小了,即array[guess] < target,则让min = guess + 1
  5. 否则,guess 太大了。 让 max = guess - 1
  6. 回到步骤2。

实现伪代码

在这些教程中, 我们将英语、伪代码和JavaScript 交替使用, 具体使用取决于具体情况。作为一名程序员, 您应该学会理解伪代码, 并能够将其转化为您选择的语言——因此, 即使我们在这里使用JavaScript,您使用其他语言实现伪代码也应该很简单。
我们如何将该伪代码转换为JavaScript程序?我们应该创建一个函数,因为我们正在编写代码接受输入参数返回一个输出,而且我们希望代码能复用在不同的输入情况下。函数的参数—让我们称该函数为binarySearch— 是一个数组和一个目标值,返回值是目标值在该数组中被找到时的位置索引。
现在, 让我们进入函数的主体, 并决定如何实现它。第6步说回到第2步。这听起来像一个循环。它应该是一个for循环或一个while循环?如果你真的想使用 for 循环, 可以, 但通过二分搜索猜测的索引并不按照索引顺序进行,for 循环并不方便。首先, 我们可以根据一些计算来猜测索引 12,然后是18。因此, 一个while循环是更好的选择。
这个伪代码缺少了一个重要的步骤, 这对猜谜游戏来说并不重要, 但对于数组的二分搜索却很重要。如果您要查找的数字 不在 数组中,会发生什么情况?让我们首先找出在这种情况下 binarySearch 函数应该返回的索引。它应该是一个不能成为数组中的合法索引的数字。我们将使用 -1, 因为这不会是任何数组中的合法索引。(实际上, 任何负数都行)。
如果没有可能的猜测, 则目标数字不在数组中。在我们的示例中, 假设我们正在primes 数组搜索目标数字10。如果10在数组中, 它将在指数3和4的值7和11之间。如果在执行 binarySearch(二分搜索) 函数时, 跟踪 minmax 的索引值, 您会发现它们最终会到达 min 等于3和 max 等于4的点。然后猜测索引 3 (因为 (3 + 4)/2 等于 3.5, 我们向下取整),并且primes[3]小于 10,然后让 min 等于4。在 minmax 均为4的情况下,只能猜测索引4,而 primes[4] 大于 10。现在 max 变为3,min 是 4,max 等于3意味着什么?这意味着, 唯一可能的猜测是至少 4, 最多是3。不存在这样的数字!因此, 我们可以得出结论,目标数字10不在primes 数组中,并且binarySearch函数将返回 -1。通常, 一旦 max 变得小于 min, 我们就知道目标数字不在有序数组中。下面是修改后的二分搜索伪代码,用于处理目标数字不存在的情况:
  1. min = 0max = n-1.
  2. 如果 max < min,则停止: target 不在当前数组 array 中。 返回 -1.
  3. 计算 maxmin 的均值作为 guess,向下取整。
  4. 如果 array[guess] 等于 target,则停止。你找到了! 返回 guess
  5. 如果 guess 太小了,即 array[guess] < target,则让 min = guess + 1
  6. 否则,guess 太大了。 让 max = guess - 1
  7. 返回步骤2
现在我们已经一起思考了伪代码, 你要尝试自己实现二分搜索。你可以回顾伪代码——事实上, 这是件好事, 因为这样你就能更好地理解将伪代码转换为程序的意义。

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

想加入讨论吗?

尚无帖子。
你会英语吗?单击此处查看更多可汗学院英文版的讨论.