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

第十四章算法（查找算法）1.顺序查找最后一个对于任意一个序列以及一个给定的元素，将给定元素与序列中元素依次比较，直到找出与给定关键字相同的元素，或者将序列中的元素与其都比较完为止。例如有20个数最优的情况是第一个就找到了即查找一次最坏的情况最后一个才找到即找了20次，下面代码就是标准的顺序查找算法功能是找到的是最后一个等于Key的位置，并用变量k记录。用flag表示是否查找到过该数importrandomn=20#待查找的数的总数key=random.randint(1,50)#生成待查找的数keyls=[random.randint(1,50)foriinrange(n)]flag=False#是否查找到key‘’k=-1#记录位置foriinrange(len(ls)):ifls[i]==key:flag=Truek=iifflag:print("查找到key的位置在",k)else:print("查无此数")2.顺序查找第一个在顺序查找中，还有一个比较特殊的存在，即查找第一个，例如有列表[1,2,2,2]需要通过顺序查找法，查找到第一个2,那么就需要在代码中控制，当第一次出现2时，就立马break出当前循环，代码如下importrandomn=20#待查找的数的总数key=random.randint(1,50)#生成待查找的数keyls=[random.randint(1,50)foriinrange(n)]flag=False#是否查找到keyforiinrange(len(ls)):ifls[i]==key:flag=Truebreakifflag:print("查找到key的位置在",i)else:print("查无此数")3.对分查找对分查找首先将查找键与有序数组内处于中间位置的元素进行比较，如果中间位置上的元素内的数值与查找键不同，根据数组元素的有序性，就可确定应该在数组的前半部分还是后半部分继续进行查找；在新确定的范围内，继续按上述方法进行查找，直到获得最终结果。对分查找有如下性质：对分查找法要求待查找的数组值是有序等。对分查找法最多比较次数为log2(n)+1对分查找法平均比较次数为3.1标准对分代码写法importrandomn=10#数的总数ls=[random.randint(20,40)foriinrange(n)]#生成随机数ls.sort()#对数组进行升序排序key=33#待查找的数(例如查找33)i,j,m,flag=0,n-1,0,False#i:起始位置游标，j:终止位置游标，m:当前对分到的位置，flag:是否查找到该值whilei<=jandflag==False:m=(i+j)//2ifls[m]==key:flag=Truebreakelifls[m]>key:j=m-1else:i=m+1ifflag:print("查找到该值，位置为",m)else:print("查无此数")例如：有数组长度为10的列表其中值分别为21,25,26,29,31,33,35,37,38,39通过对分查找算法查找33，对应的i,j,m,flag的变化如表1.1所示初值第一次第二次第三次m=0m=4m=7m=5i=0i=5i=5i=5j=9j=9j=6j=6flag=falseflag=falseflag=falseflag=true:循环退出表1.1当然，对分查找法与数据结构中的二叉树思想一致，所以我们也可以用二叉树来表示对分查找算法的对分过程。如下图图1.13.2标准对分查找变式importrandomn=10#数的总数ls=[random.randint(20,40)foriinrange(n)]#生成随机数ls.sort()#对数组进行升序排序key=33#待查找的数i,j,m=0,n-1,0#i:起始位置游标，j:终止位置游标，m:当前对分到的位置，flag:是否查找到该值whilei<=j:m=(i+j)//2ifls[m]==key:breakelifls[m]>key:j=m-1else:i=m+1ifi<=j:print("查找到该值，位置为",m)else:print("查无此数")如上述代码所示，变式和原式区别在于变式去掉的用来标识有没有找到key的flag变量计算可得当key在当前数组ls中不存在时i>j即i=j+1，当key存在于数组中时i<=j，所以在循环结束后我们可以通过i和j的关系来判断key是否存在。3.3求大于等于key的第一个数n=10#数的总数ls=[1,2,2,2,2,2,2,2,2,3]key=2i,j,m=0,n-1,0#i:起始位置游标，j:终止位置游标，m:当前对分到的位置，flag:是否查找到该值whilei<=j:m=(i+j)//2ifls[m]>=key:j=m-1else:i=m+1print("连续数的第一个位置是",i)如上述代码所示，变式和原式区别在于变式去掉的用来标识有没有找到key的flag变量以及去掉了找到后退出的代码即去掉了break。初值第一轮第二轮第三轮m0410i0001j9300表1.2设key为2时当key等于ls[m]时,j要往前走，一直走到第一个不是2的位置，即当前1的位置时，i往后走1，即i=1,所以第一个数的位置是i3.4求小于等于key的最后一个数n=10#数的总数ls=[1,2,2,2,2,2,2,2,2,3]key=2i,j,m=0,n-1,0#i:起始位置游标，j:终止位置游标，m:当前对分到的位置，flag:是否查找到该值whilei<=j:m=(i+j)//2ifls[m]>key:j=m-1else:i=m+1print("连续数的最后一个位置是",j)如上述代码所示，变式和原式区别在于变式去掉的用来标识有没有找到key的flag变量以及去掉了找到后退出的代码即去掉了break初值第一轮第二轮第三轮第四轮m04789i05899j99998表1.3设key为2时当key等于ls[m]时,i要往后走，一直走到第一个不是2的位置，即当前3的位置时，j往前走1，即j=8,所以最后一个数的位置是j3.5根据对分次数求key例：有如下代码，当c等于2的时候，key有可能是多少？importrandomc=0n=10#数的总数ls=[random.randint(20,40)foriinrange(n)]#生成随机数ls.sort()#对数组进行升序排序key=random.randint(20,40)#待查找的数i,j,m,flag=0,n-1,0,False#i:起始位置游标，j:终止位置游标，m:当前对分到的位置，flag:是否查找到该值whilei<=jandflag==False:c+=1m=(i+j)//2ifls[m]==key:flag=Truebreakelifls[m]>key:j=m-1else:i=m+1ifflag:print("查找到该值，位置为",m)else:print("查无此数")解：例如有数组长度为10的列表其中值分别为21,25,26,29,31,33,35,37,38,39,通过画二分判定树（如下），可以很显然看到c=2的时候就是对分2次，即key有可能是25或37图1.23.6根据i、j变换求key例：有如下代码，当c等于1的时候，key有可能是多少？importrandomc=0n=10#数的总数ls=[random.randint(20,40)foriinrange(n)]#生成随机数ls.sort()#对数组进行升序排序key=random.randint(20,40)#待查找的数i,j,m,flag=0,n-1,0,False#i:起始位置游标，j:终止位置游标，m:当前对分到的位置，flag:是否查找到该值whilei<=jandflag==False:m=(i+j)//2ifls[m]==key:flag=Truebreakelifls[m]>key:j=m-1