JavaScript 中的线性搜索和二进制搜索

这周我开始阅读《Grokking's Algorithms》，这是一本面向程序员和其他好奇人士的图文并茂的指南。目前为止，这本书读起来非常棒——充满了实用的例子，并配有有趣的插图，以通俗易懂的方式解释了技术概念。书中的代码示例是用 Python 编写的。我主要是一名 JavaScript 开发人员，所以我想先学习一下这本书，然后向大家展示我的 JavaScript 代码。

搜索数组

您正在列表中搜索某个东西。您不确定它是否真的在列表中，但如果在，您想知道它在哪里。在这种情况下，我们有一个彩虹，我们正在寻找一种特定的颜色。

var rainbow = ["red", "orange", "yellow", "green", "blue", "indigo", "violet"];

这 简单的 坏的直线导轨

您可能会想，“简单！我只需循环遍历数组的每个元素并返回匹配项！”这有效，称为线性搜索。

function linearSearch(arr, elToFind) {
  for (var i=0; i<arr.length; i++) {
    if (arr[i] == elToFind) {
      return i;
    }
  } return null;
}

linearSearch(rainbow, "green"); // returns 3
linearSearch(rainbow, "white"); // returns null

但是，（虽然这个数组的大小取决于你的数据集的大小）这里面存在性能方面的权衡。你必须循环遍历每个元素才能发现你的元素不在数组中。当我们只讨论 7 种颜色时，这没什么，但如果我们要遍历一个包含数千或数百万条记录的数组呢？还是算了吧。

二分查找

二分查找以已排序的数组为输入，查找特定元素。如果该元素存在于数组中，则返回元素的索引；否则返回 null。由于数组已经排序，因此查找可以将目标元素与数组中间的元素进行比较，从而一次消除一半的搜索范围。可以将其想象成一场“冷热”游戏。

使用二分查找重试彩虹示例

你我都理解前面提到的彩虹的 ROY G. BIV 排序，但你的浏览器可不是幼儿园出身。为了对彩虹进行二分查找，需要先按字母顺序排序。幸运的是，我们有 JavaScript 内置的数组排序方法。

var rainbow = ["red", "orange", "yellow", "green", "blue", "indigo", "violet"];
var sortedRainbow = rainbow.sort(); 
// returns ["blue", "green", "indigo", "orange", "red", "violet", "yellow"];

太棒了！现在我们有了可以传递给二分查找的东西。

function binarySearch(sortedArray, elToFind) {
  var lowIndex = 0;
  var highIndex = sortedArray.length - 1;
  while (lowIndex <= highIndex) {
    var midIndex = Math.floor((lowIndex + highIndex) / 2);
    if (sortedArray[midIndex] == elToFind) {
      return midIndex;
    } else if (sortedArray[midIndex] < elToFind) {
      lowIndex = midIndex + 1;
    } else {
      highIndex = midIndex - 1;
    }
  } return null;
}

var sortedRainbow = ["blue", "green", "indigo", "orange", "red", "violet", "yellow"];
binarySearch(sortedRainbow, "green"); // returns 1
binarySearch(sortedRainbow, "white") // returns null

好了，说了这么多。或许你是个搜索高手，完全理解了。让我们逐行进行二分查找。

• binarySearch函数接受一个sortedArray和一个您要搜索的元素 ( elToFind )。

  • 在搜索过程中，您将跟踪搜索的范围，其起始低索引为 0，起始高索引为排序数组中元素的数量。搜索开始时，范围将覆盖整个数组。

  • while循环一直执行，直到搜索范围缩小到一个元素

    • 找到lowIndex和highIndex之间元素的索引，计算这两个值的平均值（注意：使用 Math.floor 将此值向下舍入，因为midIndex必须是整数）
    • 如果找到了元素，则返回索引
    • 如果当前元素小于（按字母顺序排列）要搜索的元素，则将lowIndex增加到比midIndex大一
    • 如果当前元素大于（按字母顺序排列）要搜索的元素，则将highIndex减小为比midIndex小一

  • 如果元素在数组中不存在，则返回 null

下一步

既然我们已经了解了两种搜索方法（线性和二元），我们需要一种方法来衡量它们的性能。在我的下一篇文章中，我将探讨对数（回归代数2）和大O符号。敬请期待！