Python教程-在Python中的线性搜索

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

有两种类型的搜索 -

• 线性搜索
• 二分搜索

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

什么是线性搜索？

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

它将每个元素与我们要搜索的值进行比较。如果两者匹配，就找到了该元素，并且算法返回键的索引位置。

线性搜索的概念

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

步骤 - 1： 从第一个元素开始搜索，并将key = 7与列表x的每个元素进行比较。

步骤 - 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()的函数，它接受三个参数 - list1，列表的长度和要搜索的数字。我们定义了一个for循环，遍历每个元素并将其与关键字值进行比较。如果找到元素，则返回索引，否则返回-1，表示元素不在列表中。

线性搜索复杂性

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

• 基本情况 - O(1)
• 平均情况 - O(n)
• 最坏情况 - O(n)

线性搜索算法适用于较小的列表（<100），因为它会检查每个元素以获取所需的数字。假设有一个包含10,000个元素的列表，并且所需元素位于最后一个位置，那么将通过与列表的每个元素进行比较而消耗大量时间。

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

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