Python 中的线性搜索

W9XCG • 2024-10-03 23:27 • 编程

Python 是最流行和最强大的语言之一。执行代码只需要几行，这使得它成为用户友好的语言。在本教程中，我们将学习 Python 中的线性搜索。搜索是一种查找特定元素在给定列表中是否存在的技术。

有两种搜索方式-

线性搜索
二进位检索

这两种技术都广泛用于搜索给定列表中的元素。

什么是线性搜索？

线性搜索是一种在列表中查找元素的方法。这也称为顺序搜索。这是最简单的搜索算法，因为它以顺序的方式搜索所需的元素。

它将每个元素与我们正在搜索的值进行比较。如果两者都匹配，则找到元素，算法返回键的索引位置。

线性搜索的概念

让我们理解以下步骤，在给定的列表中找到元素 key = 7。

步骤- 1: 从第一个元素开始搜索，对列表 x 的每个元素检查键= 7。

步骤- 2: 如果找到元素，返回键的索引位置。

步骤 3: 如果没有找到元素，返回元素不存在。

线性搜索算法

有一个要搜索的 n 元素和键值的列表。

下面是线性搜索算法。


LinearSearch(list, key)
  for each item in the list
    if item == value
      return its index position
   return -1

Python 程序

让我们理解下面线性搜索算法的 Python 实现。

程序


def linear_Search(list1, n, key):

    # Searching list1 sequentially
    for i in range(0, n):
        if (list1[i] == key):
            return i
    return -1

list1 = [1 ,3, 5, 4, 7, 9]
key = 7

n = len(list1)
res = linear_Search(list1, n, key)
if(res == -1):
    print("Element not found")
else:
    print("Element found at index: ", res)

输出:

Element found at index:  4

说明:

在上面的代码中，我们创建了一个函数 linear_Search()，，它采用三个参数——list 1、列表长度和要搜索的数字。我们为循环定义并迭代每个元素，并与键值进行比较。如果找到元素，返回 index else return -1，这意味着元素不在列表中。

线性搜索复杂性

线性搜索算法的时间复杂度-

基本案例-0(1)
平均案例- O(n)
最坏情况-O(n)

线性搜索算法适用于较小的列表(< 100)，因为它检查每个元素以获得所需的数量。假设有 10，000 个元素列表，并且期望的元素在最后一个位置可用，通过与列表中的每个元素进行比较，这将消耗大量时间。

为了得到快速的结果，我们可以使用二分搜索算法。

我们已经讨论了线性搜索的基本概念。在下一个教程中，我们将学习第二个也是最流行的搜索算法二分搜索。

原创文章，作者：W9XCG，如若转载，请注明出处：https://www.506064.com/n/130784.html