第14章 算法（查找算法）知识点梳理—2024届高考信息技术二轮复习知识点梳理

第十四章 算法（查找算法） 1.顺序查找最后一个 对于任意一个序列以及一个给定的元素，将给定元素与序列中元素依次比较，直到找出与给定关键字相同的元素，或者将序列中的元素与其都比较完为止。 例如有20个数 最优的情况是第一个就找到了 即查找一次 最坏的情况 最后一个才找到 即找了 20次 ，下面代码就是标准的顺序查找算法功能是找到的是最后一个等于Key的位置，并用变量k记录。用flag表示是否查找到过该数 import random n=20 #待查找的数的总数 key=random.randint(1,50) #生成待查找的数key ls=[random.randint(1,50) for i in range(n)] flag=False#是否查找到key‘’ k=-1 #记录位置 for i in range(len(ls)): if ls[i]==key: flag=True k=i if flag: print("查找到key的位置在",k) else: print("查无此数") 2.顺序查找第一个 在顺序查找中，还有一个比较特殊的存在，即查找第一个，例如有列表[1,2,2,2] 需要通过顺序查找法，查找到第一个2,那么就需要在代码中控制，当第一次出现2时，就立马break出当前循环，代码如下 import random n=20 #待查找的数的总数 key=random.randint(1,50) #生成待查找的数key ls=[random.randint(1,50) for i in range(n)] flag=False#是否查找到key for i in range(len(ls)): if ls[i]==key: flag=True break if flag: print("查找到key的位置在",i) else: print("查无此数") 3.对分查找 对分查找首先将查找键与有序数组内处于中间位置的元素进行比较，如果中间位置上的元素内的数值与查找键不同，根据数组元素的有序性，就可确定应该在数组的前半部分还是后半部分继续进行查找；在新确定的范围内，继续按上述方法进行查找，直到获得最终结果。 对分查找有如下性质： 1. 对分查找法要求待查找的数组值是有序等。 2. 对分查找法最多比较次数为 3. 对分查找法平均比较次数为 3.1标准对分代码写法 import random n=10#数的总数 ls=[random.randint(20,40) for i in range(n)]#生成随机数 ls.sort() #对数组进行升序排序 key=33 #待查找的数(例如查找33) i,j,m,flag=0,n-1,0,False #i:起始位置游标，j:终止位置游标，m:当前对分到的位置，flag:是否查找到该值 while i<=j and flag==False: m=(i+j)//2 if ls[m]==key: flag=True break elif ls[m]>key: j=m-1 else: i=m+1 if flag: print("查找到该值，位置为",m) else: print("查无此数") 例如：有数组长度为10的列表 其中值分别为 21, 25, 26, 29, 31, 33, 35, 37, 38, 39 通过对分查找算法查找33，对应的i,j,m,flag的变化如表1.1所示 初值 第一次 第二次 第三次 m=0 m=4 m=7 m=5 i=0 i=5 i=5 i=5 j=9 j=9 j=6 j=6 flag=false flag=false flag=false flag=true:循环退出 表1.1 当然，对分查找法与数据结构中的二叉树思想一致，所以我们也可以用二叉树来表示对分查找算法的对分过程。如下图 图1.1 3.2标准对分查找变式 import random n=10#数的总数 ls=[random.randint(20,40) for i in range(n)]#生成随机数 ls.sort() #对数组进行升序排序 key=33 #待查找的数 i,j,m=0,n-1,0 #i:起始位置游标，j:终止位置游标，m:当前对分到的位置，flag:是否