通过JavaScript进行线性与二进制搜索

JavaScript 带有一些非常方便的开箱即用工具，用于搜索数组。但是对于大型数据集，像 indexOf、find 或基本循环这样的 O(n) 方法并不是最好的，甚至不是可行的。相反，我们可以使用二进制搜索来遍历数组，而无需查看我们显然不需要的内容，从而为我们提供 O(logn) 解决方案。

先决条件

在比较性能和复杂性时，我将使用 Big O 表示法，您可以在此处进行复习。

练习数据

以下是我将参考的一些已排序和未排序的数据集，它们都有 50 个项目。

const unsortedArr = [31, 27, 28, 42, 13, 8, 11, 30, 17, 41, 15, 43, 1, 36, 9, 16, 20, 35, 48, 37, 7, 26, 34, 21, 22, 6, 29, 32, 49, 10, 12, 19, 24, 38, 5, 14, 44, 40, 3, 50, 46, 25, 18, 33, 47, 4, 45, 39, 23, 2];

const sortedArr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50];

线性搜索

这是标准的蛮力解决方案，我敢肯定你已经做过一千次了。我们只是告诉它，“我需要一些东西，所以一个接一个地查看所有内容，直到找到它”。如果有 100 万倍以上的项目，则需要花费 100 万倍的时间，这是没有人会忍受的。数据是否排序没有区别。

const linear = (arr, target) => {
  let steps = 0;

  for (let i = 0; i < arr.length; i++) {
    steps++;
    if (arr[i] === target) return `Found: ${arr[i]} in ${steps} steps`;
  };
};

console.log(linear(unsortedArr, 40)); // 40 steps in 40 Milliseconds
console.log(linear(sortedArr, 40)); // 40 steps in 40 Milliseconds

二进制搜索

暴力破解你的方式显然是一个非常缓慢且不可扩展的解决方案。与其浪费资源查看显然不是我们想要的数据，我们可以使用“分而治之”的方法让每个操作都专注于忽略我们不想要的东西，而不是痛苦地寻找我们想要的东西。

我们有三个主要组件，两个指针和一个枢轴。每个指针都从数组的任一端开始，中心点位于中心。然后我们检查我们想要的是否高于或低于我们的枢轴，如果高于则左指针移动到枢轴的位置，而枢轴移动到新的中间。我们一直运行它，直到我们的支点等于我们的目标。

每一步我们都将我们的数据集减半，完全忽略我们不需要的，给我们一个 O(logn) 的时间复杂度。如果我们在包含 100 万个项目的数组中搜索一个数字，需要 10 步，那么 10 亿个项目的搜索可能只需要 15-20 步。

const binary = (arr, target) => {
  let start = 0;
  let end = arr.length;
  let pivot = Math.floor((start + end) / 2);
  let steps = 0;

  for (let i = 0; i < arr.length; i++) {
    if (arr[pivot] !== target) {
      if (target < arr[pivot]) end = pivot;
      else start = pivot;
      pivot = Math.floor((start + end) / 2);
      steps++;
    };

    if (arr[pivot] === target) return `Found: ${target} in ${steps} steps`;
  };

  return 'Nothing Found';
};

console.log(linear(unsortedArr, 40)); // Nothing Found
console.log(binary(arr, 44)); // 5 steps in 8 Milliseconds
console.log(binary(arr, 43)); // 2 steps in 7 Milliseconds

二进制搜索有一个很大的缺点，即只允许我们在排序后的数组上执行此操作，但是还有其他基于在搜索之前对数据进行预排序的解决方案。

结论

这只是应用二分搜索的一种方式，但只要对各种数据结构进行了排序，这个想法就可以重新配置。在未来，我希望我们可以探索使用这种技术以闪电般的速度遍历更高级的数据集⚡。