极客笔记线性搜索在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个元素的列表，所需的元素位于最后一个位置，与列表的每个元素进行比较将耗费很长时间。
为了获得快速结果，我们可以使用二分搜索算法。
我们已经讨论了线性搜索的基本概念。在下一个教程中，我们将学习第二个也是最流行的搜索算法，即二分搜索算法。