5.4.1顺序查找课件-浙教版高中信息技术选修1

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