用JavaScript编写二进制搜索算法

作者 : IT 大叔 本文共2032个字,预计阅读时间需要6分钟 发布时间: 2020-10-15

在计算机科学中,很少有工具像搜索算法那样经常使用。程序员和工程师每天都依靠它们筛选数据,并且几乎以一种或另一种方式将它们构建到几乎每种现代编程语言中。

最重要且广泛使用的搜索算法之一是二进制搜索,也称为半间隔搜索对数搜索二进制印章维基百科描述了二进制搜索的功能,如下所示:

二进制搜索将目标值与数组的中间元素进行比较。如果它们不相等,则消除目标不能位于其中的那一半,并在剩余的一半上继续搜索,再次将中间元素与目标值进行比较,并重复此过程直到找到目标值。如果搜索结束时剩下的一半为空,则目标不在数组中。

本质上,我们正在做的是每次迭代循环时将正在搜索的数组分解一半,查看该中点,然后将其与目标进行比较以查看是否应该将数组再次分解一半,以左或右。之后,我们增加或减少左右指针以缩小窗口。为了形象化它,让我们看一个例子:

array = [0, 2, 4, 7, 8, 10, 12]
target = 4

         \/ midpoint, not target
[0, 2, 4, 7, 8, 10, 12]
 ^ left              ^ right


   \/ new midpoint, not target
[0, 2, 4, 7, 8, 10, 12]
 ^     ^

      \/ new midpoint, target!
[0, 2, 4, 7, 8, 10, 12]
       ^

乍一看似乎有些奇怪,但是您考虑得越多(一旦将其放入代码中,它就会很快变得有意义)。

二进制搜索按其方式工作的关键是知道我们正在处理的整数数组已排序。这是必要的,因为我们正在将每个中点与目标进行比较,并假设当升序排序时,它将正确地位于左侧或右侧。

尽管这在某种程度上限制了使用二进制搜索的机会,但它通常是在处理排序数据时使用的绝对最佳搜索。由于将数组分解为一半,因此二进制搜索的最佳运行时复杂度为O(log n),就搜索优化而言,这是可靠的。

是时候实施了!

相对于理解核心逻辑,实现二进制搜索算法实际上非常简单,并且可以用最少14行或更少的代码行来完成。

让我们逐行构建在一起!

首先,我们将声明函数及其参数:

function binarySearch(arr, target) {

}

接下来,我们将用它们的初始值定义左右指针。在左边的指针将在阵列的起点开始,而指针将在年底开始:

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;
}

现在,我们为函数添加核心逻辑:while循环。这个while循环将被比较的值指针,继续只要跑左边小于或等于

从本质上讲,这将告诉循环运行,直到窗口“关闭”为止,这意味着我们将数组分解得尽可能小,但仍然找不到目标值。在这种情况下,我们将在循环后添加一个返回值:

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;

  while (left <= right) {

  }

  return "Target Not Found"
  // could also return -1, false, undefined, etc
}

现在我们开始循环。首先,我们将声明中点变量并计算其值,然后添加“基本情况”,该基本情况将返回一个值并在找到目标后结束该函数:

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;

  while (left <= right) {
    let mid = Math.floor((left + right) / 2);

    if (arr[mid] === target) return mid;
  }

  return "Target Not Found"
  // could also return -1, false, undefined, etc
}

在此版本的算法中,如果在数组中找到了目标值的索引,我们将简单地返回它。此返回值可以更改为您喜欢的任何值。

最后但并非最不重要的一点是,我们将实现if else语句,该语句检查目标是在中点的左侧还是右侧,并相应地增加或减少指针:

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;

  while (left <= right) {
    let mid = Math.floor((left + right) / 2);

    if (arr[mid] === target) return mid;

    if (target < arr[mid]) {
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  }

  return "Target Not Found"
  // could also return -1, false, undefined, etc
}

我们完成了!

上面的代码是完成的算法,可以在任何认为合适的地方和任何地方实现。

许多编程语言的语法都内置了二进制搜索功能,或者提供了更轻松地实现二进制搜索功能的选项,但是通过将数组分成较小的部分并比较值来了解其工作原理的核心逻辑对于技术面试和设计您的应用极为重要。拥有解决特定问题的算法。

免责声明:
1. 本站资源转自互联网,源码资源分享仅供交流学习,下载后切勿用于商业用途,否则开发者追究责任与本站无关!
2. 本站使用「署名 4.0 国际」创作协议,可自由转载、引用,但需署名原版权作者且注明文章出处
3. 未登录无法下载,登录使用金币下载所有资源。
IT小站 » 用JavaScript编写二进制搜索算法

常见问题FAQ

没有金币/金币不足 怎么办?
本站已开通每日签到送金币,每日签到赠送五枚金币,金币可累积。
所有资源普通会员都能下载吗?
本站所有资源普通会员都可以下载,需要消耗金币下载的白金会员资源,通过每日签到,即可获取免费金币,金币可累积使用。

发表评论