geekdoc-python-zh/docs/py4b/linear-search-in-python.md

Python 中的线性搜索

原文：https://www.pythonforbeginners.com/basics/linear-search-in-python

在编程的时候，你一定遇到过我们需要知道一个元素在列表中的位置的情况。为此，我们可以使用线性搜索算法。在本文中，我们将实现一个线性搜索算法，在 python 中查找列表中元素的索引。

什么是线性搜索算法？

在线性搜索算法中，我们从列表的索引 0 开始，检查元素是否出现在索引处。如果元素出现在索引处，我们将索引作为输出返回。否则，我们移动到下一个索引，直到我们找到正在被搜索的元素或者到达列表的末尾。

例如，假设给我们一个列表myList=[1,23,45,23,34,56,12,45,67,24]。

现在，我们要搜索元素 12 的索引。为此，我们将从索引 0 开始，检查 12 是否存在。如果是，我们将返回 0 作为结果，或者我们将移动到索引 1。我们将继续以这种方式移动到索引 6，其中有 12。在检查索引 6 处是否存在 12 之后，我们将返回 6 作为输出。如果任何元素不存在，我们将返回-1，这将指定该元素不在列表中。

有了线性搜索操作的概述，让我们定义线性搜索操作的算法。

线性搜索算法

线性搜索的算法可以指定如下。

**算法输入:**一个列表和一个要搜索的元素。

**输出:**元素的索引(如果元素存在的话)。否则为-1。

1. 从列表的索引 0 开始。
2. 检查元素是否出现在当前位置。
3. 如果是，返回当前索引。转到 8。
4. 检查当前元素是否是列表的最后一个元素。
5. 如果是，返回-1。转到 8。否则，转到 6。
6. 移动到列表的下一个索引。
7. 转到 2。
8. 停下来。

因为我们已经定义了线性搜索的算法，所以让我们用 python 实现它。

def LinearSearch(input_list: list, element: int):
    list_len = len(input_list)
    for i in range(list_len):
        if input_list[i] == element:
            return i
    return -1

myList = [1, 23, 45, 23, 34, 56, 12, 45, 67, 24]
print("Given list is:", myList)
position = LinearSearch(myList, 12)
print("Element 12 is at position:", position) 

输出:

Given list is: [1, 23, 45, 23, 34, 56, 12, 45, 67, 24]
Element 12 is at position: 6

线性搜索算法的缺点

线性搜索算法在时间复杂度方面是非常昂贵的。在最坏的情况下，它具有 O(n)复杂度，其中 n 是列表中元素的数量。

另一个缺点是它没有考虑列表中元素的排列。如果元素按升序排列，并且我们必须搜索最大的元素，则总是需要最大数量的步骤来产生结果。

类似地，如果一个元素不在列表中，当它遍历列表中的每个元素时，它将再次花费最大数量的步骤来产生结果。

结论

在本文中，我们讨论了线性搜索算法。我们也用 python 实现了它。要了解更多关于 python 编程的知识，你可以阅读这篇关于列表理解的文章。你可能也会喜欢这篇关于 Python 中链表的文章。