1、5.4.1 顺序查找查找又称检索，计算机根据所给条件查找出满足条件的对象，即在存储的一批数据内寻找出一个特定的数据，或者确定在该批数据内是否存在这样的数据。若没有找到满足条件的对象，则返回特定值，表明查找失败；若查找到满足条件的对象，则表明查找成功，一般要求返回该对象的存储位置或对象值本身。通常，程序将按照查找的结果（找到或未找到）来决定接着应执行后面哪一个计算步骤。顺序查找顺序查找又称线性查找，从顺序表的一端开始，依次将每个元素的关键字与给定值key（查找键）进行比较。若某个元素的关键字等于key，则表明查找成功；若所有元素都比较完毕仍找不到，则表明查找失败。如下图所示，在规模为8的数组d中
2、，分别按顺序查找算法寻找数据18和15的情况，处理过程中找到的第4个数组元素d3中的数据与18相等，表示8个数据中存在值为18的元素；而若key为15时，查找完所有数据仍未找到，表示8个数据中不存在值为15的元素。18keyd252522221313181814141111171719190 01 12 23 34 45 56 67 7到此处已找到15keyd252522221313181814141111171719190 01 12 23 34 45 56 67 7查完所有数据仍未找到顺序查找过程实例时间复杂度为时间复杂度为O(n)O(n)开始i 0in-1?di=key?i i+1是是否
3、否找到，输出信息未找到，输出信息结束顺序查找算法流程图是是否否实现此算法的Python程序如下：d=25,22,13,18,14,11,17,19key=18flag=Falselength=len(d)for i in range(length):if di=key:flag=True breakif flag=True:print(“查找成功！”)else:print(“未找到”)顺序查找算法也可以写成函数的形式，如下所示：def seq_search(s,a):length=len(s)flag=False for i in range(length):if si=a:flag=True
4、 break if flag=True:return i else:return Falsed=25,22,13,18,14,11,17,19key=15result=seq_search(d,key)print(result)小结顺序查找本质上是一种枚举算法思想，顺序查找程序就是用循环来枚举所有要查找的对象，然后在循环体内用条件判断当前枚举出的对象是否等于查找对象。假设n个数据依次存储在长度为n的数组a中，查找键为key，自定义函数seq_search(a,key)返回数组a中首个值为key的元素下标，若找不到key则返回-1。def seq_search(a,key):for i in r
5、ange(len(a):if ai=key:return i else:return-1练一练1.某个列表中共有m个元素，进行顺序查找之后查找失败，则其中元素的比较次数是（）A.m B.m2 C.m-1 D.(m+1)/2A2.有如下python程序段：a=2,6,8,8,2,4,7,3p=0for i in range(1,len(a):if aiap:p=i则运行该段代码后，变量p的值为（）A.0B.2C.3D.8B3.有如下Python程序段：key=int(input(“key=”)s=0a=for i in range(10):a.append(i+1)for i in range(
6、len(a):if ai%key=0:s=s+1print(s)当输入的key=5时，程序运行结束后，输出的值为（）A.0 B.1 C.2 D.3C4.查找一个英文句子中是否包含某个单词，可以使用顺序查找的方法，实现上述功能的Python程序段如下，请在划线处填入合适的代码。long=“I have an apple and an orange.”word=input(“输入要查找的单词：”)flag=_for i in range(len(long)-len(word):if long_=word:print(“yes”)flag=True break if flag=False:print(“no”)Falsei:i+len(word)谢 谢
