标签:Python,线性查找
线性查找算法是最简单的查找算法之一。线性查找算法的输入是一个数组或列表和项,该算法查找数组中是否存在该项。如果找到该项,则返回其索引;否则,可以返回null或你认为在数组中不存在的任何其他值。
下面是在Python中执行线性查找算法的基本步骤:
1.在数组的第一个索引(索引0)处查找输入项。
2.检查是否在当前索引中找到该项。如果是,则返回索引并转至步骤5。
3.检查当前索引是否是数组的最后一个索引。如果是,则返回null并转至步骤5。
4.移动到数组中的下一个索引并转至步骤2。
5.停止算法。
试运行线性查找算法
在Python中实现线性查找算法之前,让我们试着通过一个示例逐步了解线性查找算法的逻辑。
假设有一个整数列表,想在该列表中查找整数15。Python的设置可能如下所示:
nums = [4,9,15,21,25,28,35,38,40,45]
item = 15
迭代1
步骤1:在nums数组的第0个索引处查找项15。
步骤2:检查当前索引(索引0)中是否存在15。由于当前索引包含项4,因此不会返回true,所以进入第3步。
步骤3:检查当前索引是否是nums数组的最后一个索引。由于这也返回false,所以进入下一步。
第4步:移动到nums数组的索引1并转到下一次迭代,该迭代从第二步开始。
迭代2
步骤2:检查当前索引(索引1)中是否存在15。由于当前索引包含项9,因此不会返回true,所以进入第3步。
步骤3:检查当前索引是否是nums数组的最后一个索引。由于返回false,所以进入下一步。
第4步:移动到nums数组的索引2并转到下一次迭代,该迭代从第二步开始。
迭代3
步骤2:检查当前索引(索引2)中是否存在15。这将返回true,因为当前索引包含项15。索引2将返回给调用函数,此时将进入步骤5。
步骤5:停止算法。
在Python中实现线性查找算法
由于线性查找算法的逻辑非常简单,因此在Python中实现线性查找算法也同样简单。我们创建了一个for循环,该循环遍历输入数组。如果在该数组的任何索引处找到该项,则会打印该数组索引,中断for循环。否则,如果for循环结束并且未找到该项,则可以打印未找到该项。
下面是Python中线性查找算法的非函数实现。
nums = [4,9,15,21,25,28,35,38,40,45]
item = 38
value_found = False
for i in range(len(nums)):
if nums[i] == item:
value_found = True
print("找到该项,其索引是", i)
break
if value_found == False:
print("未找到该项")
输出如下图1所示。
图1
下面是线性查找算法的函数实现。以下脚本中的函数lin_search()接受输入数组和要查找的项作为其参数。
在该函数内部,for循环遍历输入数组的所有项。如果在任何索引中找到该项,则返回该索引值。否则,返回Null值。
def lin_search(nums, item):
for i in range(len(nums)):
if nums[i] == item:
value_found = True
return i
return None
nums = [4,9,15,21,25,28,35,38,40,45]
item = 40
index = lin_search(nums, item)
if index != None:
print("找到该项,其索引是", index)
else:
print("未找到该项")
输出如下图2所示。
图2
线性查找算法的时间复杂度为N,其中N是输入数组中的项数。在这种情况下,迭代所有数组项后,在输入数组的最后一个索引处找到该项。
显然,线性查找算法并不是查找元素在列表中位置的最有效方法,但学习如何编程线性查找的逻辑在Python或任何其他编程语言中仍然是一项有用的技能。
注:本文学习整理自wellsr.com,供有兴趣的朋友参考。