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 个元素列表，并且期望的元素在最后一个位置可用，通过与列表中的每个元素进行比较，这将消耗大量时间。
为了得到快速的结果，我们可以使用二分搜索算法。
我们已经讨论了线性搜索的基本概念。在下一个教程中，我们将学习第二个也是最流行的搜索算法二分搜索。