3.8 KiB
Python 中的线性搜索——一种实用的方法
原文：https://www.askpython.com/python/examples/linear-search-algorithm
让我们了解一下 Python 中一个简单明了的搜索算法。
线性搜索算法
线性搜索的工作方式非常类似于我们在一个随机的列表中进行搜索。
假设我们需要在给定的页面上找到一个单词，我们将从顶部开始，逐个查看每个单词，直到找到我们要找的单词。
与此类似，线性搜索从第一个项目开始，然后检查列表中的每个项目，直到找到项目或列表用尽。
让我们举一个例子:
线性搜索算法的理论示例
考虑一下，
- 名单:2000 年 19 日，8 日，2 日，99 日，24 日，17 日，15 日，88 日，40 日
- 目标:99
所以，我们需要在给定的列表中找到 99。我们从第一项开始，然后仔细检查清单上的每一项。
- 项目 1: 19，未找到。
- 第二项:2000，未找到。
- 项目 3: 8，未找到。
- 项目 4: 2，未找到。
- 项目 5，99，发现目标，结束循环。
因此，我们在位置 5 经过五次检查后找到了给定的目标。
如果给定的目标不在列表中，那么我们会遍历整个列表而找不到该项，在列表结束后，我们会将该项声明为未找到。
请注意，我们以线性方式查看列表中的每一项，这就是为什么该算法如此命名的原因。
关于效率的一个注记
线性搜索并不是一个非常有效的算法，它遍历列表中的每一项，所以算法直接受列表中项目数量的影响。
换句话说，该算法的时间复杂度为 O(n)。这意味着，如果列表中的项目数乘以一个数量，那么完成该算法所需的时间将乘以该数量。
有更好的搜索算法，如 Sentinel、 Binary 或 Fibonacci Search，但线性搜索是所有这些算法中最简单和最基本的，这意味着每个程序员都应该知道如何使用它。
用 Python 实现线性搜索算法
def linear_search(lst, target):
for i in range(len(lst)):
if(lst[i] == target):
return i
return -1
让我们看看代码，
- 我们正在创建一个接受两个参数的线性搜索函数。第一个参数是包含项目的列表，第二个参数是要查找的目标项目。
- 然后，我们用计数器
i，i创建一个循环，将保存给定列表的所有索引，即i将从 0 到列表长度-1。 - 在每次迭代中，我们都将目标与索引
i处的列表项进行比较。 - 如果它们是相同的，那么这意味着我们已经在列表中的那个索引处找到了目标，所以我们简单地返回那个索引并结束循环和函数。
- 如果检查了整个列表，但没有返回任何项，那么控件将移出列表，现在我们确信目标项不在列表中，所以我们返回-1，以此来表明没有找到该项。
让我们看看对于列表中的一个项目和不在列表中的另一个项目，算法将如何表现:
输出
Linear Search
这里，我们发送两个项目作为目标:99，它在列表中的索引 4 处，12，它不在列表中。
正如我们所看到的，算法为 99 返回了索引 4，为 12 返回了-1。这表明 99 在索引 4 处，12 不在列表中，因此算法正在工作。
结论
在本教程中，我们学习了一个非常简单的搜索算法，叫做线性搜索。
我们讨论了线性搜索是如何工作的，我们谈到了它的效率以及为什么它被命名为“线性”。
然后，我们看了算法是如何用 Python 编写的，它做了什么，并通过查看代码的输出证实了这一点。我希望你学到了一些东西，下节课再见。