二分查找算法的 JavaScript 实现

在这篇文章中，我将比较线性搜索和二分搜索算法。您将学习线性和二进制算法的伪代码，查看演示这两种方法的示例，了解时间复杂度，并获得有关如何实现算法的分步指南。

简介

作为一名程序员，您希望找到问题的最佳解决方案，以便您的代码不仅正确而且高效。选择次优算法可能意味着更长的完成时间、增加的代码复杂性，或更糟糕的是，程序崩溃。

您可能使用过搜索算法来定位数据集合中的项目。 JavaScript 语言有多种方法（例如 find）来查找数组中的项目。然而，这些方法使用线性搜索。线性搜索算法从列表的开头开始，将每个元素与搜索值进行比较，直到找到为止。

当元素数量较少时，这很好。但是，当您搜索包含数千或数百万个元素的大型列表时，您需要一种更好的方法来定位项目。这是您使用二分搜索的时候。

在本教程中，我将解释二分搜索的工作原理以及如何在 JavaScript 中实现该算法。首先，我们回顾一下线性搜索算法。

线性搜索

我们将首先解释如何在 JavaScript 中实现线性搜索。我们将创建一个名为 linearSearch 的函数，该函数接受整数或字符串和数组作为参数。该函数将在数组中的每个元素中搜索该值，如果找到，则返回该值在数组中的位置。如果数组中没有该值，则返回-1。

线性搜索的伪代码

Set found to false
Set position to −1
Set index to 0
while found is false and index < number of elements
    if list[index] is equal to search value
        Set found to true
        Set position to index
    else Add 1 to index
return position

线性搜索的逐步说明

假设我们线性搜索的输入是 [1,9,13,16,3,4,0,12]。如果我们要搜索的值是 16，则上述逻辑将返回 3。并且，如果我们搜索 11，上述逻辑将返回 -1。让我们来分解一下。

我们通过将 found 设置为 false，将 position 设置为 -1，并将 index 设置为 0 来初始化算法。然后我们迭代：

步骤	index	列表[索引]	位置	找到
1	0	1	-1	false
2	1	9	-1	false
3	2	13	-1	false
4	3	16	3	true

如果我们对数组中不存在的元素遵循上述逻辑，您将看到代码返回 -1，因为 found = false，并且 position = -1 直到最后。

线性搜索的Javascript实现

这是线性搜索算法的 JavaScript 实现：

function linearSearch(value, list) {
    let found = false;
    let position = -1;
    let index = 0;
 
    while(!found && index < list.length) {
        if(list[index] == value) {
            found = true;
            position = index;
        } else {
            index += 1;
        }
    }
    return position;
}

线性搜索的属性

需要注意的是，线性搜索算法不需要使用排序列表。此外，该算法可以定制以用于不同的场景，例如通过键搜索对象数组。如果您有一个包含名字和姓氏键的客户数据数组，您可以测试该数组是否包含具有指定名字的客户。在这种情况下，您不需要检查 list[index] 是否等于我们的搜索值，而是检查 list[index].first。

线性搜索的时间复杂度

如果搜索的元素是列表中的第一个元素，则可以实现最佳情况的时间复杂度。现在，搜索只需一次比较即可完成。因此，最好情况的时间复杂度为O(1)。

如果搜索的元素是最后一个元素或者不存在于列表中，则会出现最坏情况的时间复杂度。在这种情况下，搜索必须比较数组中的所有元素。我们说输入数据的长度为 n，这意味着由于进行了 n 次比较，总体时间复杂度为 O(n)。

在上面的示例中，我在包含八个元素的数组上使用了 linearSearch 函数。在最坏的情况下，当搜索值不在列表中或位于列表末尾时，该函数将必须进行八次比较。因为我们的数组很小，所以不需要使用不同的算法进行优化。然而，超过某一点，使用线性搜索算法就不再有效，这时使用二分搜索算法会更好。

线性搜索的平均时间复杂度也是O(n)。

线性搜索的空间复杂度

该算法的整体空间复杂度相当于数组的大小。因此，O(n)。您不需要保留任何额外的空间来完成此算法。

二分查找

假设您正在玩一个猜数字游戏。系统会要求您猜测 1 到 100 之间的一个数字。如果您的数字过高或过低，您将会得到提示。

您的策略是什么？你会随机选择数字吗？您会从 1 开始，然后是 2，依此类推，直到您猜对为止？即使您有无限的猜测，您也希望在尽可能少的尝试中做出正确的猜测。因此，您可以从猜测 50 开始。如果数字较大，您可以猜测 75。如果数字较小，则意味着数字在 50 到 75 之间，您会选择中间的数字。你会继续这样，直到得到正确的数字。这类似于二分搜索的工作原理。

有两种实现二分查找的方法：

• 迭代法
• 递归方法

迭代二分搜索的伪代码

下面是一些使用迭代方法表达二分搜索的伪代码：

do until the low and high pointers have not met or crossed
    mid = (low + high)/2
    if (x == arr[mid])
        return mid
    else if (x > arr[mid]) 
        low = mid + 1
    else                     
        high = mid - 1

递归二分搜索的伪代码

这是使用递归方法实现二分查找的伪代码。

binarySearch(arr, x, low, high)
    if low > high
        return False 
    else
        mid = (low + high) / 2 
        if x == arr[mid]
            return mid
        else if x > arr[mid]    
            return binarySearch(arr, x, mid + 1, high)
        else                              
            return binarySearch(arr, x, low, mid - 1)

无论使用何种技术，二分搜索算法始终使用分而治之的方法。

分步说明

让我们考虑一个数组 [1,9,13,16,3,5,0,12]，其中 searchValue 是 13。

我们从执行二分搜索所需的排序数组开始。请注意，对数组进行排序的成本很高，但一旦完成，就可以多次有效地搜索该数组。

现在，高指针和低指针将分别设置为第一个和最后一个元素。中间指针设置为 (low - high) / 2 给出的索引。

由于 searchValue > mid，我们需要搜索数组的右侧。因此，我们将 low 指针设置为紧接在 mid 之后，并将 mid 重置为位于 low 和 high 指针之间。

同样，目标值位于数组的右侧。我们再次调整低指针和高指针。现在低和中指针是相同的。

现在，在 mid 处找到了 searchValue，这意味着我们已经到达搜索的末尾！

步骤	low	mid	high	列表[mid]
1	0	3	7	5
2	4	5	7	9
3	6	6	7	13

二分查找的Javascript实现

现在让我们用 JavaScript 编写二分搜索算法！

我们将创建一个函数 binarySearch，它接受一个值和一个数组作为参数。如果找到该值，它将返回列表中出现该值的索引。如果没有找到该值，则返回-1。这是我们用 JavaScript 编写的实现：

//note that list must be sorted for this function to work
function binarySearch(value, list) {
    let low = 0;    //left endpoint
    let high = list.length - 1;   //right endpoint
    let position = -1;
    let found = false;
    let mid;
 
    while (found === false && low <= high) {
        mid = Math.floor((low + high)/2);
        if (list[mid] == value) {
            found = true;
            position = mid;
        } else if (list[mid] > value) {  //if in lower half
            high = mid - 1;
        } else {  //in in upper half
            low = mid + 1;
        }
    }
    return position;
}

时间复杂度

我们使用二分搜索来查找数组中的元素的主要原因之一是它的时间复杂度。在最佳情况下，二分查找的时间复杂度为O(1)。当数组中间的元素与搜索元素匹配时，就会发生这种情况。

在最坏的情况下，使用二分搜索搜索元素的时间复杂度为 O(log n) — 对于较大的 n 值，远低于 O(n)。要了解 log(n) 的增长速度比 n 慢多少，这里有一个 log(n) 典型值表.

n	日志（n）
1	1
8	3
1024	10
1,000,000	19.9
1,000,000,000,000,000,000	59.8

因此，正如您所看到的，n 越大，二分搜索相对于线性搜索的改进就越大。

对于使用二分搜索来搜索项目，平均情况时间复杂度也是O(log n)。

空间复杂度

实现二分查找的空间复杂度还是O(n)。

二分查找的属性

与线性搜索不同，二分搜索使用排序列表。这让我们可以使用“分而治之”的算法来解决问题。

结论

在本教程中，我们了解了如何实现线性搜索和二分搜索算法。线性搜索算法更简单，并且不需要排序数组。然而，使用较大的数组效率很低。在最坏的情况下，算法必须搜索所有元素进行 n 次比较（其中 n 是元素数量）。

二分查找算法则需要先对数组进行排序，并且实现起来比较复杂。然而，即使考虑到排序成本，它的效率也更高。例如，具有 10 个元素的数组对于二分搜索最多进行 4 次比较，而对于线性搜索则最多进行 10 次比较，这并不是一个很大的改进。然而，对于具有 1,000,000 个元素的数组，二分查找的最坏情况也只有 20 次比较。这相对于线性搜索来说是一个巨大的改进！

了解如何使用二分搜索不仅仅是面试问题的练习。这是一项实用技能，可以让您的代码更高效地工作。

这篇文章已根据 Divya Dev 的贡献进行了更新。 Divya 是一位拥有五年以上经验的前端开发人员。她是安娜大学的毕业生和金牌获得者。

以上是二分查找算法的 JavaScript 实现的详细内容。更多信息请关注PHP中文网其他相关文章！