Python顺序查找

查找的定义为:在一个数据元素集合中,通过一定的方法确定与给定关键字相同的数据元素是否存在于集合中。一般来说,如果查找成功,程序会返回数据的位置或相关信息;如果查找失败,则返回相应的提示。

查找的方法可以分为两种:比较查找法与计算式查找法。比较查找法基于两种数据结构:线性表和树。查找的对象(一般是由同一类型的数据元素/记录构成的集合)又可以被称为查找表。查找还分为静态查找和动态查找。对查找表进行静态查找时,程序只进行查找并返回信息;进行动态查找时,在静态查找的基础上,还增加了增删查找表中数据元素的操作。

顺序查找是所有查找方法中最基础也最简单的一种,一般用于对线性表的查找。它是按照数据在查找表中原有的顺序进行遍历查询的算法。由于需要遍历整个查找表,所以顺序查找的时间复杂度为 O(n)。

举例来说,如图 1 所示,在一个数组中,顺序查找就是按数据的下标从小到大查找。这时候,只要知道数组的长度,使用一个 for 循环就可以完成查找了。在 for 循环内部的代码根据输出要求而定。
顺序查找
图 1:顺序查找

接下来介绍两个顺序查找的例题。

【例 1】在一个已知的列表 [1,3,5,4,2,4,6,5,1] 中查找给定的元素出现的第一个位置。如果给定的元素存在于列表中,输出它的下标;如果不存在,输出 -1。输入的给定元素是 int 类型。

参考代码如下:
arr = [1,3,5,4,2,4,6,5,1]
key = int(input()) #输入关键字
for i in range(len(arr)): #顺序遍历列表
    if arr[i] == key:
        print(i)
        break #保证只输出第一个位置就跳出遍历循环
#关键字不存在于列表中
print(-1)

在这段程序中,print(-1) 只会在 for 循环被自然终止时执行。(自然终止指 i>=len(arr) 时跳出循环,而不是因为 break 结束循环)因此,当跳出 for 循环时,我们可以确定在列表中不存在与 key 相等的元素,所以输出 -1。

【例 2】在一个已知的列表 [1,3,5,4,2,4,6,5,1] 中查找给定的元素。输出给定元素出现的所有下标。若给定元素不存在于数组中,不输出。输入的给定元素是 int 类型。

参考代码如下:
arr = [1,3,5,4,2,4,6,5,1]
key = int(input()) #输入关键字
for i in range(len(arr)): #顺序遍历列表
    if arr[i] == key: #只要关键字与当前元素相等,就输出当前下标
        print(i)

不同于例 1,例 2 的代码中没有 break 语句,从而可以保证每个与 key 相等的元素的位置都被输出。

总体来说,按照数据的顺序依次查找,顺序查找就水到渠成了。