资源简介

5.3　迭代算法思想——二分查找
学习目标　
1.掌握二分查找核心算法思想,在一个[i,j]区间中,不断查找中间位置m,并不断更新查找区间(更新并画出左右端点),直到找到或区间不存在。
2.掌握利用退出语句、标志变量和循环条件不成立的结束循环两种方式。
3.掌握查找区间不存在时,根据查找键值来判断变量i、j、m的关系。
(2024年1月浙江省选考)某算法的部分流程图如图所示,若n的值为7,key的值为78,数组元素a[0]至a[n-1]依次存放7,12,24,36,55,78,83,执行这部分流程后,输出c的值为(　　)
A.0 B.1
C.2 D.3
　　在一个区间为[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肯定成立,则该数在序列中不存在。
例1 (2024年6月浙江选考)某二分查找算法的Python程序段如下:
i,j=0,len(d)-1
while i<=j:
　　m=(i+j)//2　　　　#语句①
　　if key==d[m]:
　　　　break
　　elif key　　　　j=m-1
　　else:
　　　　i=m+1
当d为[6,12,15,18,22,25,28,35,46]时,运行该程序段查找key,语句①的执行次数小于等于2;若将d修改为[6,12,15,18,22,25,28,35,46,58],重新运行该程序段,查找同一key值,则语句①的执行次数不可能为(　　)
A.1 B.2
C.3 D.4
变式1 某二分查找算法的Python程序段如下:
i,j,x=0,len(a)-1,0
while i<=j:
　　m=(i+j)//2;x+=1
　　if a[m]==key:
　　　　break
　　elif a[m]　　　　i=m+1
　　else:
　　　　j=m-1
当a的元素分别为[5,16,22,28,35,43,52,67,78,89]和[5,16,22,28,35,43,52,67,78]时,查找同一key产生的x值相同,则key的值可能是(　　)
A.52 B.39
C.58 D.70
例2 数组元素a[0]~a[n-1]已按降序排列,现要将a[pos](0≤pos≤n-1)的值加5,并保持数组的有序性不变,实现该功能的部分程序段如下,方框中应填入的正确代码为(　　)
t=a[pos]+5
L,R=0,pos-1
while L<=R:
　　m=(L+R)//2
　　if t<=a[m]:
　　　　L=m+1
　　else:
　　　　R=m-1
for i in range(　　　　　　):
　　a[i]=a[i-1]
a[i-1]=t
A.pos,R,-1 B.pos,L,-1
C.R,pos D.L,pos
变式2 某二分查找算法的Python程序段如下:
a=[1,3,5,7,8,8,8,10,12]
import random
key=random.randint(1,20)
i=0;j=8;s=""
while i<=j:
　　m=(i+j)//2
　　if a[m]>key:
　　　　j=m-1;s=s+"L"
　　else:
　　　　i=m+1;s=s+"R"
执行该程序段后,输出内容可能是(　　)
A.LR B.LLL
C.RLR D.RRRR
1.有如下Python程序段:
import random
a=['A','#','B','C','D','E','#','F']
i=0;j=len(a)-1
x=random.choice('ABCDEF')　#从字符串'ABCDEF'中随机选出一个字符
while i<=j:
　　mid=(i+j)//2
　　if a[mid]==x:
　　　　break
　　elif a[mid]=='#' or a[mid]>x:
　　　　j=mid-1
　　else:
　　　　i=mid+1
print(a[mid])
则程序运行后,输出结果不可能为(　　)
A.A B.B
C.C D.D
2.某二分查找算法的Python程序段如下:
a=[3,5,6,7,9,12,14,15,18,20]
i=0;j=9;s=""
while i<=j:
　　m=(i+j)//2
　　if key==a[m]:
　　　　break
　　if key　　　　j=m-1
　　　　s=str(a[m])+" "+s
　　else:
　　　　i=m+1
　　　　s=s+" "+str(a[m])
print(s)
执行该程序段,输入待查找的数key,则输出的内容不可能的是(　　)
A.6 5 9 B.3 5 9
C.14 15 9 12 D.9 15 18 20
3.某二分查找算法的Python程序段如下:
i=0;j=len(a)-1;n=0
while i<=j:
　　m=(i+j)//2
　　n+=1
　　if a[m]==key:
　　　　break
　　elif a[m]>key:
　　　　j=m-1
　　else:
　　　　i=m+1
列表a有8个元素,存放了互不相同的升序数字,运行该程序段查找key,n的值为2,若将加框处的代码改为m=(i+j+1)//2后,再次运行程序查找同一个key,则n的值为(　　)
A.1 B.2
C.3 D.4
4.某二分查找算法的Python程序段如下:
from random import randint
key,cnt=randint(5,9)*2+1,0
i,j=0,len(d)-1
while i<=j:
　　cnt+=1
　　m=(i+j)//2
　　if key==d[m]:break
　　if key　　　　j=m-1
　　else:
　　　　i=m+1
当d为[8,10,12,14,16,17,18,19]时,变量cnt的值不可能是(　　)
A.1 B.2
C.3 D.4
5.有如下Python程序段:
a=[100,90,15,40,72,65,32,81,6];b=[8,2,6,3,5,4,7,1,0]
i,j=0,len(a)-1
c=0;key=72
while i<=j:
　　m=(i+j)//2
　　if a[b[m]]==key:break
　　if a[b[m]]　　　　i=m+1
　　else:
　　　　j=m-1
　　　　c+=1
程序执行结束后变量c的值为(　　)
A.4 B.3
C.2 D.1
6.某二分查找算法的Python程序段如下:
n=int(input());c=0;d=[1,2,3,4,5,6]
for k in range(0,len(d),n):
　　i=0;j=len(d)-1
　　key=d[k]
　　while i<=j:
　　　　m=(i+j)//2;c+=1
　　　　if key==d[m]:
　　　　　　break
　　　　elif key　　　　　　j=m-1
　　　　else:
　　　　　　i=m+1
print(c)
执行程序段后,输入以下不同的n值,输出结果与其它三个不同的是(　　)
A.2 B.3
C.4 D.5
7.某二分查找算法的Python程序如下:
left=0;right=7;s=""
d=[14,23,29,34,38,42,52,69]
key=int(input('请输入要查找的数据'))
while left<=right:
　　mid=(left+right)//2
　　if key==d[mid]:
　　　　s=s+"M"
　　if key<=d[mid]:
　　　　right=mid-1;s=s+"L"
　　else:
　　　　left=mid+1;s=s+"R"
print(s)
执行程序段,输入待查找的数key,显示的内容可能是(　　)
A.RRRML B.LM
C.LMRL D.LRRM
8.某二分查找算法的程序如下:
i=0;j=9;c=0
key=int(input())
while i<=j:
　　m=(i+j)//2
　　if a[m]==key:
　　　　break
　　if a[m]>key:
　　　　j=m-1
　　else:
　　　　i=m+1
　　　　c+=1
若a=[2,13,14,19,23,26,29,31,32,38],运行该程序段后,c的值为2,则key的值不可能是(　　)
A.19 B.29
C.30 D.32
9.某算法的部分流程图如图所示,数组a=[24,22,20,18,15,13,11,10],若key=20,则执行这部分流程后,输出cnt的值为(　　)
A.1 B.2
C.3 D.4
10.有如下Python程序:
import random
nums=[11,23,35,44,57,68,76,89]
target=random.randint(20,70) #随机生成[20,70]区间内的一个正整数
lst=[]
left,right=0,len(nums)-1
while left<=right:
　　lst.append([left,right])　#为lst追加一个元素
　　mid=(left+right)//2
　　if nums[mid]==target:
　　　　break
　　elif nums[mid]　　　　left=mid+1
　　elif nums[mid]>target:
　　　　right=mid-1
该程序段运行后,列表lst的长度不可能为(　　)
A.1 B.2
C.3 D.4
11.列表a包含7个先升序后降序且互不相等的元素,即[1,3,5,7,6,4,2],要找到该数组的最大值位置,实现该功能的程序段如下:
L,R=1,len(a)-2
while L<=R:
　　m=(L+R)//2
　　if (1)　　　　　　:
　　　　L=m+1
　　else:
　　　　R=m-1
print((2)　　　　　　)
则加框(1)(2)处应填入的正确代码依次为(　　)
①a[m]>a[m+1]　②a[m]③L　④m　⑤R
A.①③ B.②③
C.①⑤ D.②④
12.已知非降序列表a由若干个整型元素构成,现要查找并输出a中整数key出现的次数。实现该功能的程序段如下:
def search(a,key):
　　L,R=0,len(a)-1
　　while L<=R:
　　　　m=(L+R)//2
　　　　if 　　　　　　:
　　　　　　R=m-1
　　　　else:
　　　　　　L=m+1
　　return L
#列表a和key初始化,代码略
print(search(a,key+1)-search(a,key))
加框处应填入的正确代码为(　　)
A.a[m]>=key B.a[m]>key
C.a[m]13.有如下Python程序段:
def binSearch(i,j,key):
　　if i>j:
　　　　return 0
　　m=(i+j)//2
　　if key==a[m]:
　　　　return m
　　if key　　　　return binSearch(i,m-1,key)+m
　　return binSearch(m+1,j,key)+m
n=7
a=[5,6,7,8,9,9,11]
key=int(input("输入查找键:"))
print(binSearch(0,n-1,key))
执行该程序段后,输入待查找的数,输出的结果不可能是(　　)
A.6 B.8
C.12 D.14
1.某二分查找算法的Python程序段如下:
#生成若干数据,有序排列后存储在列表d,代码略
key=int(input("输入要查找的正整数:"))
n=0
i,j=0,len(d)-1
while i<=j:
　　m=(i+j)//2
　　print(d[m],end=" ")
　　if d[m]==key:
　　　　break
　　elif d[m]　　　　i=m+1
　　else:
　　　　j=m-1;n+=1
程序运行后,变量n的值为2,输出的内容可能是(　　)
A.4 7 7 B.10 4 12
C.7 6 7 D.9 12 15 18
2.有如下Python程序段,输入正整数key值,执行该程序段,输出的值可能是(　　)
a=[6,15,18,20,25,30,35,38]
key=int(input("输入要查找的数据:"))
i=0;j=len(a)-1
s=""
while i<=j:
　　m=(i+j+1)//2
　　s+=str(a[m])+","
　　if key==a[m]:
　　　　break
　　if key　　　　j=m-1
　　else:
　　　　i=m+1
print(s[:-1])
A.25,20 B.25,18,20
C.25,15,6 D.25,30,35
3.在存储8个非降序元素的数组a中,查找key的代码如下:
key=int(input("输入要查找的数据:"))
i=0;j=len(a)-1
f=[0]*len(a)
while i<=j:
　　m=(i+j)//2
　　f[m]=1
　　if key==a[m]:
　　　　break
　　if key　　　　j=m-1
　　else:
　　　　i=m+1
print(f)
运行该程序,输出的结果可能是(　　)
A.[1,1,0,1,0,0,0,0] B.[1,1,1,1,0,0,0,0]
C.[0,0,1,1,0,0,0,0] D.[0,0,0,1,1,0,1,0]
4.某二分查找算法的Python程序段如下:
key=random.randint(2,4)*2
a=[2,5,6,8,13,15,20,22]
ans=0;i=0;j=len(a)-1
while i<=j:
　　m=(i+j)//2
　　ans+=m
　　if key==a[m]:
　　　　break
　　elif key>a[m]:
　　　　i=m+1
　　else:
　　　　j=m-1
执行该程序段后,ans的值不可能是(　　)
A.3 B.4
C.5 D.6
5.某二分查找算法的python程序如下:
f=[0]*20
i=0;j=19;n=0;m=0
while i<=j and f[m]==0:
　　m=(i+j+1)//2
　　n=n+1
　　if a[m]==key:
　　　　f[m]=1
　　elif a[m]　　　　j=m-1
　　else:
　　　　i=m+1
数组a中的元素各不相同且按降序排列,执行该程序段后n的值为4,则key的值不可能为(　　)
A.a[1] B.a[4]
C.a[12] D.a[16]
6.运行如下Python程序段,若输入“B”,则变量cnt的值为(　　)
a=['A','B','C','D','E','F','G']
ch=input("输入A-G之间的字母:")
cnt=0
for key in a:
　　i,j=0,len(a)-1
　　while i<=j:
　　　　m=(i+j)//2
　　　　if a[m]==ch:
　　　　　　cnt+=1;break
　　　　if a[m]==key:
　　　　　　break
　　　　elif a[m]　　　　　　i=m+1
　　　　else:
　　　　　　j=m-1
A.1 B.2
C.3 D.7
7.有如下Python代码:
n=int(input("请输入一个数:"))
a=[i for i in range(n)]
c=0
for i in range(1,n):
　　L=1;R=i-1
　　while L<=R:
　　　　m=(L+R)//2
　　　　if a[i]*a[m]==n:
　　　　　　c+=1;break
　　　　elif a[i]*a[m]　　　　　　L=m+1
　　　　else:
　　　　　　R=m-1
print(c)
输入36,执行程序后,输出结果是(　　)
A.1 B.2
C.3 D.4
8.某二分查找算法的程序段如下:
key=int(input('待查数据为:'))
i=0;j=10;n=0
while i<=j:
　　m=(i+j+1)//2
　　if a[m]==key:
　　　　break
　　elif a[m]>key:
　　　　j=m-1;n=n-1
　　else:
　　　　i=m+1;n=n+1
执行该程序段后,下列说法正确的是(　　)
A.该程序若要实现二分查找,要求数组a按降序排列
B.若n为-2,则查找key值可能等于a[3]的值
C.若n为2,则查找key的值可能小于a[10]
D.n的值最小为-4,最大为4
9.有如下Python程序段:
a=[90,15,40,72,59,32,81,6]
b=[7,1,5,2,4,3,6,0]
i,j=0,len(a)-1;p=-1
key=random.randint(30,60)
while i<=j:
　　m=(i+j)//2
　　if a[b[m]]==key:
　　　　p=b[m];break
　　elif a[b[m]]　　　　i=m+1
　　else:
　　　　j=m-1
print(p)
程序运行后,变量p的值不可能是(　　)
A.2 B.3
C.4 D.5
10.班里共n位同学,学号0至n-1,其中有一位同学未交作业。为了找出未交作业的同学学号,假设已交作业的n-1位同学学号从小到大存放于列表a中,则划线处代码是(　　)
L,R=0,n-2
while L<=R:
　　m=(L+R)//2
　　if a[m]==m:
　　　　①　　　　　
　　else:
　　　　②　　　　　
print(③　　　　　　)
A.①R=m-1　②L=m+1　③L
B.①R=m-1　②L=m+1　③R
C.①L=m+1　②R=m-1　③L
D.①L=m+1　②R=m-1　③R
11.有如下Python程序段:
def search(i,j):
　　while i<=j:
　　　　m=(i+j)//2
　　　　if a[m]>a[m-1] and a[m]　　　　　　i=m+1
　　　　elif a[m]a[m+1]:
　　　　　　j=m-1
　　　　else:
　　　　　　return m
a=[3,11,20,25,30,36,50,49,37,16]
print(a[search(0,9)])
程序执行后输出的结果为(　　)
A.50 B.6
C.7 D.49
12.某二分查找算法Python程序段如下:
i,j,n=0,len(a)-1,0
while i<=j:
　　m=(i+j)//2
　　if key>a[m]:
　　　　i=m+1;n+=1
　　else:
　　　　j=m-1;n-=1
当a为[0,1,2,3,4,5,6,7]时,运行该程序段查找key得到的n值,与把加框处语句改为m=(i+j+1)//2后得到的n值相等,则key可能是(　　)
A.0 B.1
C.2 D.3
13.某使用二分查找算法的Python程序段如下:
a=[21,22,23,24,25,26,27,28,29,30]
key=int(input("key="))
c=0
i,j=0,9
m=(i+j)//2
while i<=j and key!=a[m]:
　　if a[m]　　　　i=m+1
　　else:
　　　　j=m-1
　　m=(i+j)//2
　　c+=1
print(c)
若程序运行后,输出结果是3,则key的值可能是(　　)
A.21或23 B.24或27
C.26或29 D.23或30
14.有如下Python程序段:
#随机产生10个整型元素的非降序序列,依次存入列表a(a[0]!=a[9]),代码略
key=int(input())
i=0;j=len(a)-1
n=0
while i<=j:
　　m=(i+j)//2
　　n+=1
　　if a[m]　　　　i=m+1
　　else:
　　　　j=m-1
执行上述程序段后,下列说法不正确的是(　　)
A.a[i+1]可能等于key
B.a[j]可能等于key
C.i 一定等于j+1
D.n的值一定大于2
15.有如下Python程序段:
k=randint(0,2)*2
i=0;j=6;cnt=0
while i<=j:
　　cnt=cnt+1
　　m=(i+j)//2
　　if a[m]==a[k]:
　　　　break
　　if a[m]　　　　i=m+1
　　else:
　　　　j=m-1
数组元素 a[0]到a[6]各不相同且按升序排列,执行该程序段,下列说法不正确的是(　　)
A.m的值不可能为6
B.cnt的值一定为3
C.变量i、j的值一定相同
D.i的值可能小于m
16.有如下Python程序:
import random
i,j=0,len(a)-1
key=random.randint(1,47)
while i<=j:
　　mid=(i+j)//2　　　　　#语句①
　　if a[mid]<=key:　　　#语句②
　　　　i=mid+1
　　else:
　　　　j=mid-1
print(j)
当a为[5,12,19,26,33,33,48,50],运行程序,下列说法正确的是(　　)
A.语句①执行的次数可能为4
B.语句①改为“mid=(i+j+1)//2”,程序结果不会改变
C.语句②改为“a[mid]D.若生成的key是33,则输出结果是4
17.某对分查找算法的Python程序段如下:
d=[7,12,18,25,39,58,61,72,86]
key=int(input())
i,j,n=0,8,0
f=[0]*9
while i<=j:
　　m=(i+j)// 2
　　n+=1
　　if d[m]==key:break
　　if key　　　　j=m-1;f[m]=-1
　　else:
　　　　i=m+1;f[m]=1
print(n,sum(f))
执行上述程序段后,下列说法正确的是(　　)
A.若输入的key为58,则sum(f)的值为1
B.若n的值为4,则key可能的值是[40,45]
C.sum(f)的最大值可能为3
D.f[0]到f[8]各元素值可能的是0,0,0,0,1,0,1,-1,0
18.有如下Python程序段:
import random
a=[10,20,31,31,31,40,50,60]
key=random.randint(5,30)*2+1
i=0;j=len(a)-1
whilei<=j:
　　m=(i+j)//2
　　if key>a[m]:
　　　　i=m+1
　　else:
　　　　j=m-1
执行该程序段后,i的值可能是(　　)
A.0 B.3
C.4 D.8
19.有如下Python程序段:
#随机产生包含10个整型元素的升序序列,依次存入列表a,代码略
i,j=0,len(a)-1
key=int(input())
b=[]
while i<=j:
　　m=(i+j)//2
　　b.append(a[m])
　　if a[m]>key:
　　　　j=m-1
　　else:
　　　　i=m+1
print(b)
运行该程序段后,b的结果不可能是(　　)
A.[18,6,2] B.[20,9,13,18]
C.[14,21,22] D.[23,30,25,22]
20.有如下Python程序:
a=[10,11,12,12,12,17,17,17,20,21]
key=int(input("key="))
q=[0]*len(a)
L=R=len(a)//2
i,j=0,len(a)-1
while i<=j:
　　m=(i+j)//2
　　if a[m]>key:
　　　　j=m-1
　　　　L-=1;q[L]=m
　　else:
　　　　i=m+1
　　　　R+=1;q[R]=m
print(q[L:R+1])
运行程序,输入key值,则输出结果不可能为(　　)
A.[0,1,4,0] B.[1,4,0,0]
C.[9,0,4,7,8] D.[7,0,4,5]
21.某二分查找算法用于查找非降序序列arr中小于等于key的最后一个元素位置,Python代码如下:
arr=[1,1,4,4,4,5,5,5]
key=int(input())
L=0;R=len(arr)-1
while (1)　　　　　　:
　　mid=(L+R)//2
　　if (2)　　　　　　:
　　　　L=mid+1
　　else:
　　　　R=mid-1
print(R)
划线(1)(2)处可供选择的语句有:
①L④arr[mid]<=key
则正确的代码应为(　　)
A.①③ B.①④
C.②③ D.②④5.3　迭代算法思想——二分查找
学习目标　
1.掌握二分查找核心算法思想,在一个[i,j]区间中,不断查找中间位置m,并不断更新查找区间(更新并画出左右端点),直到找到或区间不存在。
2.掌握利用退出语句、标志变量和循环条件不成立的结束循环两种方式。
3.掌握查找区间不存在时,根据查找键值来判断变量i、j、m的关系。
(2024年1月浙江省选考)某算法的部分流程图如图所示,若n的值为7,key的值为78,数组元素a[0]至a[n-1]依次存放7,12,24,36,55,78,83,执行这部分流程后,输出c的值为(　　)
A.0 B.1
C.2 D.3
答案　B
解析　本题考查二分查找算法。变量c表示移动左边界向右查找的次数。查找78的过程为先找到36,向查查找1次,找到78,结束查找。
　　在一个区间为[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肯定成立,则该数在序列中不存在。
例1 (2024年6月浙江选考)某二分查找算法的Python程序段如下:
i,j=0,len(d)-1
while i<=j:
　　m=(i+j)//2　　　　#语句①
　　if key==d[m]:
　　　　break
　　elif key　　　　j=m-1
　　else:
　　　　i=m+1
当d为[6,12,15,18,22,25,28,35,46]时,运行该程序段查找key,语句①的执行次数小于等于2;若将d修改为[6,12,15,18,22,25,28,35,46,58],重新运行该程序段,查找同一key值,则语句①的执行次数不可能为(　　)
A.1 B.2
C.3 D.4
思维点拨
明考向 本题考查二分查找算法
精点拨 当d为[6,12,15,18,22,25,28,35,46]时,运行该程序段查找key,语句①的执行次数小于等于2,画出如图a所示的搜索树,则查找的key可能是22,12和28。若将d修改后的搜索树如图b所示,只有查找28时,查找的次数不一样,图b中查找28为4次,因此不可能是3次
答案　C
变式1 某二分查找算法的Python程序段如下:
i,j,x=0,len(a)-1,0
while i<=j:
　　m=(i+j)//2;x+=1
　　if a[m]==key:
　　　　break
　　elif a[m]　　　　i=m+1
　　else:
　　　　j=m-1
当a的元素分别为[5,16,22,28,35,43,52,67,78,89]和[5,16,22,28,35,43,52,67,78]时,查找同一key产生的x值相同,则key的值可能是(　　)
A.52 B.39
C.58 D.70
答案　B
解析　考查二分查找算法的应用。根据数组a的元素与二分查找时查找次数的不同绘制出如右图所示的二叉树,不同的层次表示不同的访问次数。从图中可以快速统计出查找次数。查找52时,在第一个数组里需要查找4次,在第二个数组里只需查找2次。查找58时,在第一个数组里需要查找4次,在第二个数组里只需查找3次。查找52时,在第一个数组里需要查找4次,在第二个数组里只需查找2次。查找70时,在第一个数组里需要查找3次,在第二个数组里需要查找4次。B选项查找39时,两个数组都是查找3次。
例2 数组元素a[0]~a[n-1]已按降序排列,现要将a[pos](0≤pos≤n-1)的值加5,并保持数组的有序性不变,实现该功能的部分程序段如下,方框中应填入的正确代码为(　　)
t=a[pos]+5
L,R=0,pos-1
while L<=R:
　　m=(L+R)//2
　　if t<=a[m]:
　　　　L=m+1
　　else:
　　　　R=m-1
for i in range(　　　　　　):
　　a[i]=a[i-1]
a[i-1]=t
A.pos,R,-1 B.pos,L,-1
C.R,pos D.L,pos
思维点拨
明考向 本题考查二分查找及数据元素的移动。先找到要插入的位置L,再将索引位置L至pos-1上的数据向右移动,最后再将t的值存储到a[L]中。当查找的数与a[m]相等时,还要向右继续查找,即查找的极右值,R指向最后一个相等的数据,L就是要插入位置。查找结束后,L等于R+1。若t在数组找不到,则R就是第一个比t大的数的位置
精 点 拨 A 第1次将pos-1位置上的值移动到pos位置上,最后一次将R位置上的值移动到L上,并将t存储在R位置上,不符合题意
B i的终值为L+1,将L位置移动L+1位置上,再将t存储在L位置上
C 从左向右移动,会将后面所有的值替换为a[R]
D 从左向右移动,会将后面所有的值替换为a[L]
答案　B
变式2 某二分查找算法的Python程序段如下:
a=[1,3,5,7,8,8,8,10,12]
import random
key=random.randint(1,20)
i=0;j=8;s=""
while i<=j:
　　m=(i+j)//2
　　if a[m]>key:
　　　　j=m-1;s=s+"L"
　　else:
　　　　i=m+1;s=s+"R"
执行该程序段后,输出内容可能是(　　)
A.LR B.LLL
C.RLR D.RRRR
答案　D
解析　考查二分查找算法的应用。画出对应的二叉树,如图所示。A选项由于找到后还要往右查找,因此至少查找3次。B选项若查找的数据为1,找到后还要向右查找,因此是LLR,查找的数不可能小于1。C选项第1次查找到数据8,向右查找,比8大,只可能再次向右,不可能再左查找。D选项查找大于或等于12的数,将显示RRRR。
1.有如下Python程序段:
import random
a=['A','#','B','C','D','E','#','F']
i=0;j=len(a)-1
x=random.choice('ABCDEF')　#从字符串'ABCDEF'中随机选出一个字符
while i<=j:
　　mid=(i+j)//2
　　if a[mid]==x:
　　　　break
　　elif a[mid]=='#' or a[mid]>x:
　　　　j=mid-1
　　else:
　　　　i=mid+1
print(a[mid])
则程序运行后,输出结果不可能为(　　)
A.A B.B
C.C D.D
答案　 B
解析　本题考查二分查找的算法思想。根据题目要求,画出相应的二叉树,当找到#号时,向左查找,因此不可能找到B。
2.某二分查找算法的Python程序段如下:
a=[3,5,6,7,9,12,14,15,18,20]
i=0;j=9;s=""
while i<=j:
　　m=(i+j)//2
　　if key==a[m]:
　　　　break
　　if key　　　　j=m-1
　　　　s=str(a[m])+" "+s
　　else:
　　　　i=m+1
　　　　s=s+" "+str(a[m])
print(s)
执行该程序段,输入待查找的数key,则输出的内容不可能的是(　　)
A.6 5 9 B.3 5 9
C.14 15 9 12 D.9 15 18 20
答案　A
解析　若向左查找,将找到的数a[m]连接在s的前面,向右查找连接在后面,找到后退出,不显示,根据查找算法,画出二叉树如图所示:A选项第1次查找的数是6,第2次为5,则第4次不可能比6小。B选项查找比3小的数,依次访问9,5,3,将这些数反向连接到s中。C选项查找13,s的值依次为"9","15 9","15 9 12","14 15 9 12"。D选项查找比20大的数,每次均正向连接。
3.某二分查找算法的Python程序段如下:
i=0;j=len(a)-1;n=0
while i<=j:
　　m=(i+j)//2
　　n+=1
　　if a[m]==key:
　　　　break
　　elif a[m]>key:
　　　　j=m-1
　　else:
　　　　i=m+1
列表a有8个元素,存放了互不相同的升序数字,运行该程序段查找key,n的值为2,若将加框处的代码改为m=(i+j+1)//2后,再次运行程序查找同一个key,则n的值为(　　)
A.1 B.2
C.3 D.4
答案　C
解析　查找的数据存储在a[0]至a[7]中,查找2次找到的数据分别是a[1]和a[5],修改后,a[1]和a[5]分别查找3次。
4.某二分查找算法的Python程序段如下:
from random import randint
key,cnt=randint(5,9)*2+1,0
i,j=0,len(d)-1
while i<=j:
　　cnt+=1
　　m=(i+j)//2
　　if key==d[m]:break
　　if key　　　　j=m-1
　　else:
　　　　i=m+1
当d为[8,10,12,14,16,17,18,19]时,变量cnt的值不可能是(　　)
A.1 B.2
C.3 D.4
答案　A
解析　cnt用于统计对分查找次数,key的值是[11,13,15,17,19],根据代码画出二叉树如图所示:
查找11,13,15需3次。查找17需2次,查找19需4次,因此cnt不可能为1。
5.有如下Python程序段:
a=[100,90,15,40,72,65,32,81,6];b=[8,2,6,3,5,4,7,1,0]
i,j=0,len(a)-1
c=0;key=72
while i<=j:
　　m=(i+j)//2
　　if a[b[m]]==key:break
　　if a[b[m]]　　　　i=m+1
　　else:
　　　　j=m-1
　　　　c+=1
程序执行结束后变量c的值为(　　)
A.4 B.3
C.2 D.1
答案　D
解析　数组b是对数组a的索引排序结果,a[b[i]]=[6,15,32,40,65,72,81,90,100]。查找值72,依次查找65,81和72,向右查找2次,向左查找1次。
6.某二分查找算法的Python程序段如下:
n=int(input());c=0;d=[1,2,3,4,5,6]
for k in range(0,len(d),n):
　　i=0;j=len(d)-1
　　key=d[k]
　　while i<=j:
　　　　m=(i+j)//2;c+=1
　　　　if key==d[m]:
　　　　　　break
　　　　elif key　　　　　　j=m-1
　　　　else:
　　　　　　i=m+1
print(c)
执行程序段后,输入以下不同的n值,输出结果与其它三个不同的是(　　)
A.2 B.3
C.4 D.5
答案　C
解析　A选项步长为2,将查找1,3,5,总共查找次数为5。B选项步长为3,将查找1,4,总共查找次数为5。C选项步长为4,将查找1,5,总共查找次数为4。D选项步长为1,将查找1,6,总共查找次数为5。
7.某二分查找算法的Python程序如下:
left=0;right=7;s=""
d=[14,23,29,34,38,42,52,69]
key=int(input('请输入要查找的数据'))
while left<=right:
　　mid=(left+right)//2
　　if key==d[mid]:
　　　　s=s+"M"
　　if key<=d[mid]:
　　　　right=mid-1;s=s+"L"
　　else:
　　　　left=mid+1;s=s+"R"
print(s)
执行程序段,输入待查找的数key,显示的内容可能是(　　)
A.RRRML B.LM
C.LMRL D.LRRM
答案　A
解析　根据算法画出二叉树如图所示找到后并不结束循环。
8.某二分查找算法的程序如下:
i=0;j=9;c=0
key=int(input())
while i<=j:
　　m=(i+j)//2
　　if a[m]==key:
　　　　break
　　if a[m]>key:
　　　　j=m-1
　　else:
　　　　i=m+1
　　　　c+=1
若a=[2,13,14,19,23,26,29,31,32,38],运行该程序段后,c的值为2,则key的值不可能是(　　)
A.19 B.29
C.30 D.32
答案　C
解析　根据列表a的值,画出如图所示二叉树,当向右查找时,c的值增加1,查找29,向右查找2次,若查找30,在查找29的基础上,再向右查找一次,因此需查找3次。
9.某算法的部分流程图如图所示,数组a=[24,22,20,18,15,13,11,10],若key=20,则执行这部分流程后,输出cnt的值为(　　)
A.1 B.2
C.3 D.4
答案　C
解析　算法实现采用二分查找极左值,当找到key后,并未结束查找,而是向左继续查找,直到区间不存在。第1次查找时,i=0,j=7 m=4,a[m]=15;第2次i=0,j=3,m=2,a[m]=20。第3次i=3,j=3,m=3,a[m]=18,结束查找。
10.有如下Python程序:
import random
nums=[11,23,35,44,57,68,76,89]
target=random.randint(20,70) #随机生成[20,70]区间内的一个正整数
lst=[]
left,right=0,len(nums)-1
while left<=right:
　　lst.append([left,right])　#为lst追加一个元素
　　mid=(left+right)//2
　　if nums[mid]==target:
　　　　break
　　elif nums[mid]　　　　left=mid+1
　　elif nums[mid]>target:
　　　　right=mid-1
该程序段运行后,列表lst的长度不可能为(　　)
A.1 B.2
C.3 D.4
答案　D
解析　本题考查二分查找。列表长度就是二分查找的查找次数。列表共8个元素,最少1次,最多4次。查找到76时,不可能继续往右查找,所以 4次是不可能的。
11.列表a包含7个先升序后降序且互不相等的元素,即[1,3,5,7,6,4,2],要找到该数组的最大值位置,实现该功能的程序段如下:
L,R=1,len(a)-2
while L<=R:
　　m=(L+R)//2
　　if (1)　　　　　　:
　　　　L=m+1
　　else:
　　　　R=m-1
print((2)　　　　　　)
则加框(1)(2)处应填入的正确代码依次为(　　)
①a[m]>a[m+1]　②a[m]③L　④m　⑤R
A.①③ B.②③
C.①⑤ D.②④
答案　B
解析　当a[m]处于上升段,满足条件a[m]12.已知非降序列表a由若干个整型元素构成,现要查找并输出a中整数key出现的次数。实现该功能的程序段如下:
def search(a,key):
　　L,R=0,len(a)-1
　　while L<=R:
　　　　m=(L+R)//2
　　　　if 　　　　　　:
　　　　　　R=m-1
　　　　else:
　　　　　　L=m+1
　　return L
#列表a和key初始化,代码略
print(search(a,key+1)-search(a,key))
加框处应填入的正确代码为(　　)
A.a[m]>=key B.a[m]>key
C.a[m]答案　A
解析　计算key+1和key的最左边位置差值就是key的个数,因此该题需查找极左值,因此当找到key时,将修改R的值,继续向左查找。
13.有如下Python程序段:
def binSearch(i,j,key):
　　if i>j:
　　　　return 0
　　m=(i+j)//2
　　if key==a[m]:
　　　　return m
　　if key　　　　return binSearch(i,m-1,key)+m
　　return binSearch(m+1,j,key)+m
n=7
a=[5,6,7,8,9,9,11]
key=int(input("输入查找键:"))
print(binSearch(0,n-1,key))
执行该程序段后,输入待查找的数,输出的结果不可能是(　　)
A.6 B.8
C.12 D.14
答案　B
解析　本题考查递归法二分查找,找到后返回中间位置,没有找到,累加找过的位置m。用索引位置画出二叉树为,没有一处分支节点和为8。
1.某二分查找算法的Python程序段如下:
#生成若干数据,有序排列后存储在列表d,代码略
key=int(input("输入要查找的正整数:"))
n=0
i,j=0,len(d)-1
while i<=j:
　　m=(i+j)//2
　　print(d[m],end=" ")
　　if d[m]==key:
　　　　break
　　elif d[m]　　　　i=m+1
　　else:
　　　　j=m-1;n+=1
程序运行后,变量n的值为2,输出的内容可能是(　　)
A.4 7 7 B.10 4 12
C.7 6 7 D.9 12 15 18
答案　A
解析　本题考查二分查找算法。如果条件d[m]2.有如下Python程序段,输入正整数key值,执行该程序段,输出的值可能是(　　)
a=[6,15,18,20,25,30,35,38]
key=int(input("输入要查找的数据:"))
i=0;j=len(a)-1
s=""
while i<=j:
　　m=(i+j+1)//2
　　s+=str(a[m])+","
　　if key==a[m]:
　　　　break
　　if key　　　　j=m-1
　　else:
　　　　i=m+1
print(s[:-1])
A.25,20 B.25,18,20
C.25,15,6 D.25,30,35
答案　B
解析　根据二分法查找算法画出对应的二叉树,可以得到遍历的路径。
3.在存储8个非降序元素的数组a中,查找key的代码如下:
key=int(input("输入要查找的数据:"))
i=0;j=len(a)-1
f=[0]*len(a)
while i<=j:
　　m=(i+j)//2
　　f[m]=1
　　if key==a[m]:
　　　　break
　　if key　　　　j=m-1
　　else:
　　　　i=m+1
print(f)
运行该程序,输出的结果可能是(　　)
A.[1,1,0,1,0,0,0,0] B.[1,1,1,1,0,0,0,0]
C.[0,0,1,1,0,0,0,0] D.[0,0,0,1,1,0,1,0]
答案　A
解析　本题考查二分查找算法的程序实现。根据题意,画出查找的二叉树如图所示,当找到某个数字时,数组f中该数字对应索引位置上值赋值为1。A选项分别访问索引3,1,0。B选项分别访问索引3,2,1,0,但该路径不存在。C选项分别访问索引3,2,该路径也不存在。D选项分别访问索引3,4,6,该路径也不存在。
4.某二分查找算法的Python程序段如下:
key=random.randint(2,4)*2
a=[2,5,6,8,13,15,20,22]
ans=0;i=0;j=len(a)-1
while i<=j:
　　m=(i+j)//2
　　ans+=m
　　if key==a[m]:
　　　　break
　　elif key>a[m]:
　　　　i=m+1
　　else:
　　　　j=m-1
执行该程序段后,ans的值不可能是(　　)
A.3 B.4
C.5 D.6
答案　C
解析　画出相应的二叉树如图所示。
若要查找4,查找的索引位置之和依次为3+1+0=4;若查找6,索引位置之和依次为3+1+2=6;查找8,m的值为3。
5.某二分查找算法的python程序如下:
f=[0]*20
i=0;j=19;n=0;m=0
while i<=j and f[m]==0:
　　m=(i+j+1)//2
　　n=n+1
　　if a[m]==key:
　　　　f[m]=1
　　elif a[m]　　　　j=m-1
　　else:
　　　　i=m+1
数组a中的元素各不相同且按降序排列,执行该程序段后n的值为4,则key的值不可能为(　　)
A.a[1] B.a[4]
C.a[12] D.a[16]
答案　D
解析　本题考查二分算法以及二分判定树。根据本题代码m=(i+j+1)//2,画出二分判定树,位于二分判定树第4层的节点下标分别是1、4、7、9、12、14、17、19所以key的值不可能是a[16]。
6.运行如下Python程序段,若输入“B”,则变量cnt的值为(　　)
a=['A','B','C','D','E','F','G']
ch=input("输入A-G之间的字母:")
cnt=0
for key in a:
　　i,j=0,len(a)-1
　　while i<=j:
　　　　m=(i+j)//2
　　　　if a[m]==ch:
　　　　　　cnt+=1;break
　　　　if a[m]==key:
　　　　　　break
　　　　elif a[m]　　　　　　i=m+1
　　　　else:
　　　　　　j=m-1
A.1 B.2
C.3 D.7
答案　C
解析　由7个字母构成一个搜索二叉树,如图所示,遍历树中每个节点,若搜索路径包含字母ch,则cnt的值增加1,查找BAC时包含字母B的节点个数。
7.有如下Python代码:
n=int(input("请输入一个数:"))
a=[i for i in range(n)]
c=0
for i in range(1,n):
　　L=1;R=i-1
　　while L<=R:
　　　　m=(L+R)//2
　　　　if a[i]*a[m]==n:
　　　　　　c+=1;break
　　　　elif a[i]*a[m]　　　　　　L=m+1
　　　　else:
　　　　　　R=m-1
print(c)
输入36,执行程序后,输出结果是(　　)
A.1 B.2
C.3 D.4
答案　C
解析　本题考查二分查找。程序的功能是数组a的i索引前找一个数,满足a[i]*a[m]==n的个数,因此分别是9*4、12*3、18*2。
8.某二分查找算法的程序段如下:
key=int(input('待查数据为:'))
i=0;j=10;n=0
while i<=j:
　　m=(i+j+1)//2
　　if a[m]==key:
　　　　break
　　elif a[m]>key:
　　　　j=m-1;n=n-1
　　else:
　　　　i=m+1;n=n+1
执行该程序段后,下列说法正确的是(　　)
A.该程序若要实现二分查找,要求数组a按降序排列
B.若n为-2,则查找key值可能等于a[3]的值
C.若n为2,则查找key的值可能小于a[10]
D.n的值最小为-4,最大为4
答案　C
解析　本题考查二分查找算法。A选项由条件a[m]>key可以看出数组是升序。B选项查找a[3]需访问a[5]→a[2]→a[4]→a[3],则n的值为-1。C选项由访问路径 a[5]→a[8]→a[10]→a[9]→end,则n的值为n值为2。D选项如果要n的值最小为-4,最大为4,至少节点数满15个,本题节点数只有11个。
9.有如下Python程序段:
a=[90,15,40,72,59,32,81,6]
b=[7,1,5,2,4,3,6,0]
i,j=0,len(a)-1;p=-1
key=random.randint(30,60)
while i<=j:
　　m=(i+j)//2
　　if a[b[m]]==key:
　　　　p=b[m];break
　　elif a[b[m]]　　　　i=m+1
　　else:
　　　　j=m-1
print(p)
程序运行后,变量p的值不可能是(　　)
A.2 B.3
C.4 D.5
答案　B
解析　本题考查索引排序和二分查找算法。key值在30-60(60取不到),在列表a中只有40、 59、32 符合范围,对应的索引值为2,4,5。
10.班里共n位同学,学号0至n-1,其中有一位同学未交作业。为了找出未交作业的同学学号,假设已交作业的n-1位同学学号从小到大存放于列表a中,则划线处代码是(　　)
L,R=0,n-2
while L<=R:
　　m=(L+R)//2
　　if a[m]==m:
　　　　①　　　　　
　　else:
　　　　②　　　　　
print(③　　　　　　)
A.①R=m-1　②L=m+1　③L
B.①R=m-1　②L=m+1　③R
C.①L=m+1　②R=m-1　③L
D.①L=m+1　②R=m-1　③R
答案　C
解析　共有n-2位学生交作业,当条件a[m]==m成立,说明未交作业的学生在后半段,因此移到L,反之向左查找R=m-1。考虑查找结束的极限情况,L必定指向不符合条件的第一个位置,即所找同学学号。
11.有如下Python程序段:
def search(i,j):
　　while i<=j:
　　　　m=(i+j)//2
　　　　if a[m]>a[m-1] and a[m]　　　　　　i=m+1
　　　　elif a[m]a[m+1]:
　　　　　　j=m-1
　　　　else:
　　　　　　return m
a=[3,11,20,25,30,36,50,49,37,16]
print(a[search(0,9)])
程序执行后输出的结果为(　　)
A.50 B.6
C.7 D.49
答案　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。
12.某二分查找算法Python程序段如下:
i,j,n=0,len(a)-1,0
while i<=j:
　　m=(i+j)//2
　　if key>a[m]:
　　　　i=m+1;n+=1
　　else:
　　　　j=m-1;n-=1
当a为[0,1,2,3,4,5,6,7]时,运行该程序段查找key得到的n值,与把加框处语句改为m=(i+j+1)//2后得到的n值相等,则key可能是(　　)
A.0 B.1
C.2 D.3
答案　C
解析　先画出两种 m计算对应的对分查找树如下:采用二分查找某个数,当找到后,示没有退出,而是向左继续查找,虚线表示0-3最后查找的位置。查找2得到的n值境外为-1。
13.某使用二分查找算法的Python程序段如下:
a=[21,22,23,24,25,26,27,28,29,30]
key=int(input("key="))
c=0
i,j=0,9
m=(i+j)//2
while i<=j and key!=a[m]:
　　if a[m]　　　　i=m+1
　　else:
　　　　j=m-1
　　m=(i+j)//2
　　c+=1
print(c)
若程序运行后,输出结果是3,则key的值可能是(　　)
A.21或23 B.24或27
C.26或29 D.23或30
答案　B
解析　代码中c记录查找的次数,但根据while语句,当key与a[m]相等时会停止循环,因此找存在于a中的数时输出的c值会比实际查找次数少一次,选项中的数据都存在于a中,输出结果为3,说明需要查找4次a[m],根据二叉树可知找24、27和30处于二叉树第四层。
14.有如下Python程序段:
#随机产生10个整型元素的非降序序列,依次存入列表a(a[0]!=a[9]),代码略
key=int(input())
i=0;j=len(a)-1
n=0
while i<=j:
　　m=(i+j)//2
　　n+=1
　　if a[m]　　　　i=m+1
　　else:
　　　　j=m-1
执行上述程序段后,下列说法不正确的是(　　)
A.a[i+1]可能等于key
B.a[j]可能等于key
C.i 一定等于j+1
D.n的值一定大于2
答案　B
解析　本题考查二分查找。当找到key后并没结束查找,而是向左继续查找,因此i 一定等于j+1,查找的是最左边的极值,a[i]可能等于key,则于a[i]和a[i+1]可能相等,a[i+1]可能等于key;但a[j]绝对不可能等于key。10个元素对应的二叉树有4层,3层为满二叉树,因此至少查找3次。
15.有如下Python程序段:
k=randint(0,2)*2
i=0;j=6;cnt=0
while i<=j:
　　cnt=cnt+1
　　m=(i+j)//2
　　if a[m]==a[k]:
　　　　break
　　if a[m]　　　　i=m+1
　　else:
　　　　j=m-1
数组元素 a[0]到a[6]各不相同且按升序排列,执行该程序段,下列说法不正确的是(　　)
A.m的值不可能为6
B.cnt的值一定为3
C.变量i、j的值一定相同
D.i的值可能小于m
答案　D
解析　本题考查二分查找的算法思想。查找的k值为0,2,4,即a[0]、a[2]、a[4]中的一个数,画出判定二叉树。由图可知,查找次数cnt均为3次,m只能是0,2,4。查找的值发生在叶子节点,因此区间中只剩下最后一个数,i,j,m的值是相等的。
16.有如下Python程序:
import random
i,j=0,len(a)-1
key=random.randint(1,47)
while i<=j:
　　mid=(i+j)//2　　　　　#语句①
　　if a[mid]<=key:　　　#语句②
　　　　i=mid+1
　　else:
　　　　j=mid-1
print(j)
当a为[5,12,19,26,33,33,48,50],运行程序,下列说法正确的是(　　)
A.语句①执行的次数可能为4
B.语句①改为“mid=(i+j+1)//2”,程序结果不会改变
C.语句②改为“a[mid]D.若生成的key是33,则输出结果是4
答案　B
解析　画出对应的二叉树如图所示。A选项只在大于等于48的数才需查找4次。B选项查找的次数可能不一样,但查找结果是一样的。C选项数组a中有2个33,修改前查找极右值,j的值为5。修改后查找极左值,j的值为3。
17.某对分查找算法的Python程序段如下:
d=[7,12,18,25,39,58,61,72,86]
key=int(input())
i,j,n=0,8,0
f=[0]*9
while i<=j:
　　m=(i+j)// 2
　　n+=1
　　if d[m]==key:break
　　if key　　　　j=m-1;f[m]=-1
　　else:
　　　　i=m+1;f[m]=1
print(n,sum(f))
执行上述程序段后,下列说法正确的是(　　)
A.若输入的key为58,则sum(f)的值为1
B.若n的值为4,则key可能的值是[40,45]
C.sum(f)的最大值可能为3
D.f[0]到f[8]各元素值可能的是0,0,0,0,1,0,1,-1,0
答案　D
解析　画出二叉树如图所示。A选项查找58,f列表的和为0。B选项若n的值为4,key可能[19,38]或[73,86]或大于86。C选项f列表的和最大值为查找大于86的数,值为4。D选项当key的取值范围在(61,72)时,f的结果为[0,0,0,0,1,0,1,-1,0]。
18.有如下Python程序段:
import random
a=[10,20,31,31,31,40,50,60]
key=random.randint(5,30)*2+1
i=0;j=len(a)-1
whilei<=j:
　　m=(i+j)//2
　　if key>a[m]:
　　　　i=m+1
　　else:
　　　　j=m-1
执行该程序段后,i的值可能是(　　)
A.0 B.3
C.4 D.8
答案　D
解析　当找到key时还要移动j向左移动继续查找,循环结束后i大于j。A选项由于key最小为11,大于a[0],必定要移动i,B和C选项索引为2、3、4的元素值均为31,查找31的极左值位置,因此i的值为2。D选项查找key的值为61时,i的值为8。
19.有如下Python程序段:
#随机产生包含10个整型元素的升序序列,依次存入列表a,代码略
i,j=0,len(a)-1
key=int(input())
b=[]
while i<=j:
　　m=(i+j)//2
　　b.append(a[m])
　　if a[m]>key:
　　　　j=m-1
　　else:
　　　　i=m+1
print(b)
运行该程序段后,b的结果不可能是(　　)
A.[18,6,2] B.[20,9,13,18]
C.[14,21,22] D.[23,30,25,22]
答案　D
解析　画出如下图所示二叉树。A选项依次访问数可能是a[4],a[1],a[0]。B选项依次访问数可能是a[4],a[1],a[2],a[3]。C选项依次访问数可能是a[4],a[7],a[8],查找的数是7。D选项第1次访问23,接着向右查找,因此不可能访问22。
20.有如下Python程序:
a=[10,11,12,12,12,17,17,17,20,21]
key=int(input("key="))
q=[0]*len(a)
L=R=len(a)//2
i,j=0,len(a)-1
while i<=j:
　　m=(i+j)//2
　　if a[m]>key:
　　　　j=m-1
　　　　L-=1;q[L]=m
　　else:
　　　　i=m+1
　　　　R+=1;q[R]=m
print(q[L:R+1])
运行程序,输入key值,则输出结果不可能为(　　)
A.[0,1,4,0] B.[1,4,0,0]
C.[9,0,4,7,8] D.[7,0,4,5]
答案　D
解析　程序的功能将查找索引m的值保存到列表q中。若a[m]大于key,L向左移动,并将m存入q[L]。若a[m]小于等于key,R向右移,将m存入q[R]。L和R的初值均为5,若第1次查找后向左查找,则m(值为4)存入q[4];若第1次查找后向右查找,则m(值为4)存入q[6],q[5]的值为0;。最终输出q[l:r+1]的值。A选项查找比10小的数,依次向左查找。B选项查找10,依次查找a[4],a[1],接着向右访问,因此位置0将保存在q[6]中。C选项查找方向依次为右,右,右,左,即查找20。D选项第2次查找必定是a[1]或a[7],依次查找a[4],a[7],a[5],而找到a[7]后必定要向右继续查找,不可以再向左查找。
21.某二分查找算法用于查找非降序序列arr中小于等于key的最后一个元素位置,Python代码如下:
arr=[1,1,4,4,4,5,5,5]
key=int(input())
L=0;R=len(arr)-1
while (1)　　　　　　:
　　mid=(L+R)//2
　　if (2)　　　　　　:
　　　　L=mid+1
　　else:
　　　　R=mid-1
print(R)
划线(1)(2)处可供选择的语句有:
①L④arr[mid]<=key
则正确的代码应为(　　)
A.①③ B.①④
C.②③ D.②④
答案　D
解析　考查二分查找算法的变式,要实现查找有边界,关键在于如何更新左右指针L和R。通常情况下,循环条件应该是L<=R(②),这样可以确保即使L和R指向同一个元素时也会进行检查。当arr[mid]和key相等时,还要移动L继续向右查找。

展开更多......

收起↑