在Python中实现线性查找

标签：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，供有兴趣的朋友参考。