Javascript

Javascript 中的二分查找

Posted by cl9000 on October 16, 2020

至繁归于至简

介绍

搜索是计算机科学领域中最常执行的任务之一。存在许多算法和数据结构来提高搜索效率。

在本文中，我们将了解二分查找背后的思想以及如何在 JavaScript 中实现它。

二分查找是一种非常简单、直观但高效的搜索算法。唯一需要注意的是，它仅适用于已排序的数组，因此可能需要对我们的数据进行一些预处理以对其进行排序。

了解二分查找

二分查找是一种分而治之的算法，每次检查数组的元素是否是我们正在寻找的元素时，它都会将数组大致分成两半。

换句话说，我们将问题分解为更简单的问题，直到它变得足够简单以直接解决它们。让我们假设我们有一个已排序的数组（按升序），然后看看二分查找的步骤：

  1. 找到给定数组的中间元素。
  2. 将中间元素与我们要查找的值（称为key）进行比较。
    • 如果键小于中间元素，则在左半部分搜索。
    • 如果键值大于中间元素，则在右半部分搜索。
    • 如果键值等于中间元素，则返回中间元素的索引值。
  3. 继续执行步骤1、2，直到只剩下一个元素。
  4. 如果仍然没有找到键，则返回-1。

JavaScript中二分查找的实现

现在我们已经了解了二进制搜索背后的逻辑，让我们在 JavaScript 中实现它：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function binarySearch(sortedArray, key){
    let start = 0;
    let end = sortedArray.length - 1;

    while (start <= end) {
        let middle = Math.floor((start + end) / 2);

        if (sortedArray[middle] === key) {
            // found the key
            return middle;
        } else if (sortedArray[middle] < key) {
            // continue searching to the right
            start = middle + 1;
        } else {
            // search searching to the left
            end = middle - 1;
        }
    }
true// key wasn't found
    return -1;
}

在这里，我们使用两个变量来跟踪我们正在搜索的当前子数组的start和end。我们找到中间元素，然后检查它是否等于、小于或大于key。

如前所述，假设我们有一个已排序的数组，我们可以丢弃数组中的一半元素。我们通过更改start或end变量在代码中完成此操作，具体取决于我们继续搜索的位置。如果我们正在查看的当前元素小于键，我们将更 start 改为 middle + 1 并有效地丢弃当前元素和所有小于该值的元素。

二分查找的效率

二分查找的时间复杂度为 O(log 2 n)，其中 n 是数组中的元素数。与时间复杂度为 O(n) 的线性搜索相比，这要好得多。与许多其他搜索算法一样，二分查找是一种就地算法。这意味着它直接在原始数组上工作，而不进行任何复制。

但是，我们必须记住，二分查找仅适用于已排序的数组。如果使用高效的排序算法，排序步骤本身的复杂度为O(nlogn)。这意味着在大多数情况下，如果数组很小，或者如果我们只需要搜索一次，蛮力（例如线性搜索）算法可能会更好。

鉴于此，当我们需要对大型数组进行重复搜索时，二分查找真的很受欢迎。如前所述，对于 11 个元素的数组，我们只需要 4 次比较（比较是所有搜索算法中最密集的任务）。然而，如果我们有一个包含 10,000,000 个元素的数组，我们只需要检查 24 个元素，即整个数组的 0.0002%。

总结

在本文中，我们研究了二分搜索。它简单、直观、高效的逻辑和实现使其成为演示分而治之策略的非常流行的算法。

参考

关注【公众号】，了解更多。


赏 支付宝打赏 微信打赏

赞赏一下 坚持原创技术分享，您的支持将鼓励我继续创作！



FEATURED TAGS
Javascript
FRIENDS