Javascript

Javascript 中的线性搜索

Posted by cl9000 on October 30, 2020

达到完美境界并不是无以复加，而是无可去除。——<安托万·德·圣·埃克苏佩里>

介绍

在计算机科学的上下文中，搜索是定位给定列表/数组中特定元素的过程。如果我们密切关注，我们可以在任何地方找到搜索算法。

考虑一下登录一个网站的过程。输入的电子邮件和密码将根据数据库中现有的键值对进行搜索，以验证用户。

在本文中，让我们看看搜索给定元素列表的最基本算法—线性搜索。

理解线性搜索

线性搜索算法是一组指令，用来遍历给定列表并检查列表中的每个元素，直到找到我们要找的元素。我们要找的元素的技术术语是- key。

该算法从最左边(或起始)元素开始，继续搜索，直到找到所需的元素或遍历列表中的所有元素。

如果找到了该元素，则返回该元素的位置(或索引)。如果要查找的元素在列表中不存在，则通常返回 -1 。

用JavaScript实现线性搜索

我们可以使用 for 循环遍历给定列表。让我们看看线性搜索的实现:

1
2
3
4
5
6
7
8
function linearSearch(arr, key){
    for(let i = 0; i < arr.length; i++){
        if(arr[i] === key){
            return i
        }
    }
    return -1
}

这里我们将遍历数组中的所有元素，并将每个元素与键进行比较。如果找到匹配，则返回元素的下标。
在本例中，变量 i s跟踪我们在数组中的位置，如果找到匹配，就返回 i 的当前值。

如果元素在我们的列表中不存在，线性搜索函数 不会从循环中返回任何 i 值。我们只是在循环之后 return -1 来表示函数没有找到所需的元素。

全局线性搜索

在前面的实现中，我们在第一次遇到要查找的元素(key)后返回一个值。但是如果我们想要一个给定元素的所有索引呢?

这就是全局线性搜索的切入点。它是线性搜索的一种变体，我们在其中寻找一个给定元素的多次出现。

让我们看看全局线性搜索的实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function globalLinearSearch(arr, key){
    let results = []
    for(let i = 0; i < arr.length; i++){
        if(arr[i] === key){
            results.push(i)
        }
    }
    // If results array is empty, return -1
    if(!results){
        return -1
    }

    return results
}

在本例中，不是立即返回匹配元素的索引，而是将其存储在一个数组中。最后，返回下标数组。

线性搜索的效率

线性搜索是蛮力算法的一个经典例子。这意味着该算法没有使用任何逻辑来尝试快速完成它应该做的事情，或者以某种方式减少它在其中搜索键的元素范围。其他搜索算法的目标是通过对列表/数组进行某种预处理(例如排序)来更有效地完成这一工作。

线性搜索的时间复杂度是 O(n)，其中 n 是我们要搜索的列表中的元素个数。这是因为我们在计算时间复杂度时总是考虑最坏的情况。在线性搜索的情况下(与大多数搜索算法一样)，最坏的情况是元素不存在于列表中。在这种情况下，我们需要遍历 n 个元素来确定这个元素不存在。

总结

在本文中，我们已经了解了线性搜索背后的逻辑，然后使用这些知识，我们用 JavaScript实现了算法。我们还研究了线性搜索算法的时间复杂度。

到目前为止，这是一种简单的搜索算法，它没有使用任何逻辑来尝试并放弃搜索的特定范围或专注于速度

参考

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


赏 支付宝打赏 微信打赏

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



FEATURED TAGS
Javascript
FRIENDS