资源简介 专题18 查找算法学业要求 知 识 点 学业水平等级1.掌握对分查找的核心算法思想并用程序代码实现 42.掌握利用二叉树来描述查找的路径或区间 4知识点一 二分查找的算法思想【知识梳理】1.________又称检索,计算机根据所给条件查找出满足条件的对象,即在存储的一批数据内寻找出一个特定的数据,或者确定在该批数据内是否存在这样的数据。若没有找到满足条件的对象,则返回特定值,表明查找失败;若查找到满足条件的对象,则表明查找成功,一般要求返回该对象的存储位置或对象值本身。2.________________又称线性查找,从顺序表的一端开始,依次将每个元素的关键字与给定值key(查找键)进行比较。若某个元素的关键字等于key,则表明查找成功;若所有元素都比较完毕仍找不到,则表明查找失败。3.________________又称折半查找,对分查找。它是一种效率很高的查找算法,但被查找的数据序列必须是有序的。4.二分查找首先将查找键与____________处于________的元素进行比较,如果中间位置上的元素的数值与查找键不同,根据数组元素的有序性,就可确定在数组的________还是________继续查找;在新确定的范围内,继续按上述方法进行查找,直到获得最终结果。5.二分查找算法描述:在一个区间为[i,j]的有序数据序列a中查找一个数据key,先确定区间的中间位置m,让key与a[m]比较,若两者相等,表示找到数据,结束查找;若中间位置的数a[m]不是要查找的数,把区间分为[i,m-1]和[m+1,j]两部分。若查找的数据在右半段,修改左边界i的值为m+1,继续往右查找;若查找的数据在左半段,修改右边界j的值为m-1,继续往左查找;修改边界后,若i大于j,则查找的区间为空,等式i=j+1肯定成立,则该数在序列中不存在。【经典案例】二分查找中间位置m的计算公式为m=(i+j)//2和m=(i+j+1)//2,当i+j为奇数时,两者没有区别;当i+j为偶数时,中间位置有两个,前者是中间偏左,后者是中间偏右。利用判定二叉树快速解题,同时确定查找路径。当查找中间结点时,还可以继续查找,因此查找不成功一定发生在叶子结点。在查找一个数的路径确定每次查找的数位置和值,可以判断查找次数,若在找不到该数据时,可以判断此时变量i、j和m的值。大致可以分为以下几种情况:①随机给出查找值,求查找次数或查找路径;②给出查找次数或查找路径,求查找值的范围;③当查找成功时没有结束查找,求查找次数或查找的边界值。【例1】 有如下Python程序段:import randoma=['A','#','B','C','D','E','#','F']i=0j=len(a)-1x=random.choice('ABCDEF') #从字符串'ABCDEF'中随机选出一个字符while i<=j:mid=(i+j)//2if a[mid]==x: breakelif a[mid]=='#' or a[mid]>x:j=mid-1else:i=mid+1print(a[mid])则程序运行后,输出结果不可能为( )A.A B.BC.C D.D思维点拨明考向 本题考查二分查找的算法思想精点拨 根据题目要求,画出相应的二叉树,当找到#号时,向左查找,因此不可能找到B。听课笔记:________________________________________________________________________________________________________________________________________________________________________________________________________【变式1】 有如下Python程序:import randomnums=[11,23,35,44,57,68,76,89]target=random.randint(20,70) #随机生成[20,70]区间内的一个正整数lst=[]left,right=0,len(nums)-1while left<=right:lst.append([left,right]) #为lst追加一个元素mid=(left+right)//2if nums[mid]==target: breakelif nums[mid] left=mid+1elif nums[mid]>target: right=mid-1该程序段运行后,列表lst的长度不可能为( )A.1 B.2C.3 D.4【例2】 有如下Python程序:import randoma=[15,18,25,34,38,40,55,61,80,85]key=random.randint(15,55)f=[0]*10i=0;j=len(a)-1while i<=j:m=(i+j+1)//2if a[m]>key:j=m-1else:if a[m]%5==0: f[m]=1i=m+1执行该程序段后,列表 f 值可能是( )A.[0,0,1,0,0,1,0,0,0,0]B.[0,0,0,0,0,1,0,0,1,0]C.[1,0,1,0,0,0,0,0,0,0]D.[0,0,0,0,0,1,1,0,0,0]思维点拨明考向 本题考查二分查找算法的算法思想精点拨 f[m]赋值语句的执行条件a[m]<=key and a[m]%5==0,即向右查找过程中,节点是5的倍数。产生数的范围是[15,55],那么只可能查找[40,55]之间的数,第1次向右查找的节点为40,第2次查找的节点是55,即只能查找55听课笔记:_________________________________________________________________________________________________________________________________________________________________________________________________________【变式2】 有如下Python程序段:import randoma=[1,3,3,8,8,10,10,14,16,17]key=random.randint(0,9)*2ans=-1;f=0L=0;R=9while L<=R:m=(L+R+1)//2if a[m]==key:ans=mbreakif a[m]>key:R=m-1f-=1else:L=m+1f+=1运行该程序段后,关于f和ans的结果,下列说法正确的是( )A.f可能的最小值为-3B.f的值可能为-1C.ans的值可能为1D.ans的值不可能为3知识点二 极值查找【知识梳理】1.查找结束可能是2种情况,一是当a[m]和key相等时,找到要查找的元素,采用________语句退出循环,二是查找的区间________存在,即左区间i大于右区间j。2.在一个非降序序列中查找一个不存在的数key时,查找的区间不断地缩小,最后一次查找时,区间中只有________个元素,即左区间i等于右区间j。若a[m]大于key,则移动右区间j,左区间i保持不变,此时变量j=i-1;若a[m]小于key,则移动左区间i,右区间保持j不变,此时变量i=j+1。因此二分查找算法结束后,若查找的数据不存在,肯定有i=________的等量关系。3.当一个非降序序列中存在多个与key相等的数据时,若要找到第1个小于key或者最左边的key,称为左极值,算法为:当a[m]________于key时,并没有采用break语句退出循环,而是继续向左查找,由于找到后,j向左移动,因此j不可能指向key,最左边key位置为i。4.右极值指的是要找到第1个大于key或者最右边的key,算法为:当a[m]等于key时,继续向________查找,由于找到后,i向右移动,因此i不可能指向key,最右边key位置为j。【经典案例】当一个非降序序列中存在多个连续相等的数据key时,若要查找最左边key,设置的查找条件为当a[m]==key时,还需移动j为m-1继续向左查找,当i>j即i=j+1时,查找的区间不存在,此时j指向的就是第1个小于等于key的值;若要查找最右边的key,当查找成功时,还需移动i为m+1继续向右查找,此时i指向的就是第1个大于等于key的值。【例题】 某对分查找算法的Python程序如下:left=0;right=7;s=″″d=[14,23,29,34,38,42,52,69]key=int(input('请输入要查找的数据'))while left<=right:mid=(left+right)//2if key==d[mid]: s=s+″M″if key<=d[mid]: right=mid-1;s=s+″L″else: left=mid+1;s=s+″R″该程序段执行后,显示的内容可能是( )A.RRRML B.LMC.LMRL D.LRRM思维点拨明考向 根据算法画出二叉树如图所示找到后并不结束循环精点拨 A 查找数据69,查找路径34,42,52,3次向右移动,第4次找到了B 查找数据23,但是找到23后,还是要向左查找,直至区间不存在,即LMLRC 查找数据23,但是找到23后,还是要向左查找,不是向右查找D 向左找到23,向右找到29,再向右查找比29大比34小的数,不可能再次向右查找听课笔记:_________________________________________________________________________________________________________________________________________________________________________________________________________【变式】 某Python程序段如下:import randoma=[0]*8;a[0]=1for i in range(1,8):a[i]=a[i-1]+random.randint(1,10)n=0;key=5i,j=0,7while i<=j:m=(i+j)//2;n+=1if a[m]<=key: i=m+1else: j=m-1print(n)执行该程序段后,输出的结果是( )A.1 B.2C.3 D.41.在7个有序的数列“a1,a2,a3,a4,a5,a6,a7”中,采用二分查找法查找数值key,依次需要进行比较的数据可能是( )A.a4 B.a4,a6,a2C.a4,a2,a5 D.a4,a6,a5,a72.有如下Python程序段:import randomd=[28,37,39,42,45,50,70,80]i,j,n=0,len(d)-1,0key=random.randint(20,35)*2while i<=j:m=(i+j)//2;n+=1if key==d[m]:breakelif keyj=m-1else:i=m+1print(i,j,m,n)执行该程序段后,下列说法正确的是( )A.n的值可能为4B.若n值为2,则必定满足i<=jC.m的值可能为1D.若n值为3,则key的值可能是453.有如下Python程序段:import randoma=[90,15,40,72,59,32,81,6]b=[7,1,5,2,4,3,6,0]i,j=0,len(a)-1key=random.randint(30,60)p=-1while i<=j:m=(i+j)//2if a[b[m]]==key:p=b[m]breakelif a[b[m]]i=m+1else:j=m-1print(p)程序运行后,变量p的值不可能是( )A.2 B.3C.4 D.54.有如下Python程序段:def search(i,j):while i<=j:m=(i+j)//2if a[m]>a[m-1] and a[m] i=m+1elif a[m]a[m+1]: j=m-1else: return ma=[3,11,20,25,30,36,50,49,37,16]print(a[search(0,9)])程序执行后输出的结果为( )A.50 B.6 C.7 D.495.某对分查找的Python程序如下:from random import randinta=[19,17,16,14,13,11,9,7]key=randint(0,4)*2+9i=0;j=7;c=0while i<=j:c=c+1m=(i+j)//2if a[m]>key:i=m+1else:j=m-1该程序段执行后,下列说法不正确的是( )A.j的值可能为1 B.c的值一定等于3C.i的值一定等于j+1 D.i的值一定不等于76.某二分查找算法的Python程序如下:import randomkey=random.randint(0,4)*2+5n=10ans=0a=[4,5,5,8,9,11,11,13,15,17]i=0j=n-1while i<=j:m=(i+j)//2if a[m]<=key:i=m+1else:j=m-1ans+=a[m]print(ans)程序运行后,输出ans的值不可能是( )A.19 B.27C.37 D.447.如下Python程序实现的功能是:在非递增数组a中查找最后一个大于等于key的元素下标。#读取一批非递增的数据保存在数组a中,代码略key=int(input(″请输入待查找的数据:″))L,R=0,len(a)-1while L<=R:m=(L+R)//2if ①________:L=m+1else:②________if R==-1:print(″不存在大于等于%d的数″%key)else:print(f″最后一个大于等于%s的元素下标是%d″%(key,③________))划线处的内容是( )A.①a[m]>key ②R=m ③mB.①a[m]>key ②R=m-1 ③mC.①a[m]>=key ②R=m-1 ③RD.①a[m]>=key ②R=m ③R8.某Python程序如下:a=[86,75,58,46,20,18,12,5]key=int(input())n=0;i=0;j=len(a)-1while i<=j:m=(i+j)//2if key>a[m]:j=m-1;n=n-1else:i=m+1;n=n+1当输入不同的 key 值,运行该程序段后,n的值可能有( )A.5种 B.6种C.7种 D.8种专题18 查找算法知识点一知识梳理1.查找(Search)2.顺序查找(Sequential Search)3.二分查找(Binary Search)4.有序数组内 中间位置 前半部分 后半部分经典案例例1 B变式1 D [本题考查二分查找。画出二叉树,随机生成[20,70]区间内的一个正整数,最少查找1次,最多4次,但查找大于76的数时,才要查找4次。每查找一次,将查找的区间添加到lst中,所以长度4次是不可能的。]例2 D变式2 D [查找一个0~18之间的随机偶数key,画出相应的二叉树。A选项查找0,向左查找4次,f的值为-4。B选项向右查找1次,找到的数为3,不是偶数。C选项a[1]的值为3,不是偶数。D选项ans的值若为3,a[3]的值为8,而找到的第1个8的索引位置是4。]知识点二知识梳理1.break 不 2.一 j+1 3.等 4.右经典案例例题 A变式 C [本题考查二分查找。根据题意画出判定二叉树如图所示。如果条件a[m]<=key成立,还要向右继续查找,因此除了查找大于等于a[6]的数据,均要查找3次,a[0]的值1,随机产生一个比前一项至少大1的数,因此a[6]至少是7,只需找3次。]当堂过关检测1.A [本题考查二分查找的算法思想。第1次查找的是最中间的节点a4,因此A选项正确。B选项a2比a4小,查找到a6后,不可再去找a2。C选项a5比a4大,也不可能。D选项第3次查找,要么a5或a7,不可能2个数同时被查找到。]2.B [本题考查二分查找算法思想。key是[40,70]区间的偶数,n是循环次数。画出相应的二叉树。最多查找3次;a[1]为37,查找的位置不可能是1。若查找2次,说明查找的数是50,中间退出循环,满足条件i<=j。]3.B [本题考查索引排序和二分查找算法。key值在30-60,在列表a中只有40、59、32符合范围,对应的索引值为2、4、5。]4.A [本题考查二分查找以及其变式。a[m-1],a[m],a[m+1]如果是连续上升的序列,往后找i=m+1 a[m-1],a[m],a[m+1]如果是连续下降的序列,往前找j=m-1,a[m-1],a[m],a[m+1]如果不满足连续上升或者下降,则直接输出m。]5.A [本题考查二分查找算法思想。数组a为降序数列,key的取值范围是9~17之间的奇数,当找到key时不要向左继续查找,结束查找时,j小于i,且i等于j+1,位置i是最接近要查找的。A选项查找17,j的值为0,查找15,j的值为2。D选项key最小值是9,因此i的值最大值是6。]6.A [本题考查二分查找算法。变量key的值可能是[5,7,9,11,13],ans是查找值的累加和。当找到key时,还要向右边界继续查找。当key=5、7时,a[m]分别是:9、5、5、8,ans=27,由此可以推断不可能是19。]7.C [查找最后一个大于等于该数应该是查找右极值,即找到后还要向右查找。最终R指向是要查找的数。]8.A [本题考查二分查找。中点计算方式为左偏,查找二叉树如下:变式在于相等不退出,而是继续向右找,key为任意数,无论是否找到,最终都从虚线处走出。向左加1,向右减1,分析二叉树可知,n值可能为:-3,-1,1,2,4这5种。] 展开更多...... 收起↑ 资源预览