资源简介

课时36 二分查找与查找树
一、二叉判定树
1. 二分查找过程可用一棵二叉树来描述，一棵子树表示一个查找区间，子树中的每个根节点对应当前查找区间的　　　　 ，子树的左子树和右子树分别对应该区间的左半部分和右半部分。
2. 对一个升序数组 a=[11,15,22,38,45,47,53,81,87,90]进行二分查找，查找键 key=53，则可作如图所示的二叉判定树。
中点元素
1. 二分查找是在有序表上进行的，所以其对应的判定树就是一棵二叉排序树。二叉排序树既能实现排序功能，也能实现查找功能，故其也称为二叉查找树。
2. 二叉排序树的排序功能主要通过二叉树的建立和遍历过程来实现，其在建立过程中要始终满足如下性质：
（1）若它的左子树不为空，则左子树上所有节点的值均　　　　它的根节点的值。
（2）若它的右子树不为空，则右子树上所有节点的值均　　　　它的根节点的值。
（3）它的左右子树也分别为二叉排序树。
3. 查找过程：首先将给定值和根节点的关键字比较，若相等，则查找成功；若不相等，则根据给定值和根节点关键字之间的大小关系，在左子树和右子树中继续进行查找。若查到为空树时，说明该树中没有待查记录，查找失败。
小于
二、二叉排序树
大于
4.二叉判定树的特点。
（1）二叉判定树是一棵二分查找判定树，也是一棵二叉排序树。
（2）判定树中的节点与序列中的数据一一对应，判定树中的节点都能查找成功。
（3）在二分查找判定树中，某节点所在的层数即是查找该节点的　　　　。
（4）判定树的　　　　 即是在该序列中进行二分查找最多的次数。
（5）从根节点开始到达某个节点的路径即是二分查找到该节点的路径。
比较次数
深度
按非降序排序的整型数组 a 的值依次为 10、25、30、41、47、50、61、x、70、87。执行该程序段后，若输入 key 的值为 67，则输出的结果是 RRL，则 x 的可能值的个数为 （　　）
A.5 B.6 C.8 D.9
典例 1 ［2025 嘉兴检测］某二分查找算法的部分 Python 程序段如下：
def search(a,key):
i=0;j=len(a)-1;s=""
while i<=j:
m=(i+j)//2
if a[m]==key:
return s
elif key s+="L";j=m-1
else:
s+="R";i=m+1
return s
key=int(input("请输入待查数据："))
result=search(a,key)
print(result)
B
√
胜券点拨1
明考向
本题考查二分查找的程序实现
审关键
s表示查找路径
考场思
维快闪
数组a的值为[10,25,30,41,47,50,61,x,70,87]，其对应的二分查找树如图所示。根据代码可知，二分查找过程中，若往左查找，则连接字符"L"；若往右查找，则连接字符"R"。输出结果为RRL，说明查找到数据47、x、70，因此key的值大于x，即x小于67，再结合a为非降序排序的整型数组，故x的值可能是61、62、63、64、65、66
典例 2 某二分查找算法的 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
elif 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
√
胜券点拨2
明考向
本题考查二分查找的程序实现
审关键
二分查找判定树
考场思
维快闪
根据程序可画出如图所示的二分查找判定树。分析程序可知，变量cnt用于统计查找次数，即对应树中的层数，key是[11,19]范围内的奇数，11、13、15在第3层退出，17在第2层退出，19在第4层退出，故cnt的值不可能为1
典例 3 ［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
C
√
胜券点拨3
明考向
本题考查二分查找的程序实现
审关键
二分查找判定树
考场思
维快闪
当d为[6,12,15,18,22,25,28,35,46]时，其对应的二分查找判定树如图a所示，语句①的执行次数小于等于2，即查找次数小于等于2，故key在二叉树中的层数小于等于2，即key的值可能是22、12、28。若将d修改为[6,12,15,18,22,25,28,35,46,58]，其对应的二分查找判定树如图b所示，22、12、28三个数对应的层数即是语句①的执行次数，分别是1、2、4，故不可能是3
1.某算法的部分流程图如图所示，若a=[8,7,6,5,4,3,2,1]，执行这部分流程后，输出c的值为10，则输入的key值为（　　）
A.8
B.10
C.2
D.任意值
该算法的作用是利用二分查找算法在序列a中查找目标元素key，元素c记录查找路径中访问过的所有元素和，元素flag标记是否已经查找到该元素。查找过程结束后，若查找成功则输出c的值，若不成功则输出-1。根据序列a画出如下二分查找判定树，故当key=2时，c的值是10。
C
√
2.某二分查找算法的Python程序段如下：
a=[1,3,3,5,5,7,8,9,9,10]
i,j=0,len(a)-1
while i<=j:
m=(i+j)//2
if key j=m-1　#语句①
else:
i=m+1　#语句②
执行该程序段后，若语句①执行了2次，语句②执行了1次，则key的值可能是
（　　）
A.5或7 B.1或3
C.5或1 D.3或7
根据数组a的值可画出如图所示的二分查找判定树，当中点元素的值等于key时，继续向右查找。语句①执行了2次，说明往左子树方向走了两步，语句②执行了1次，说明往右子树方向走了一步，故key的值可能是1或5。
C
√
3.有如下Python程序段：
import random
key=random.randint(1,3)*7
ans=""
a=[3,5,7,8,10,15,16]
i=0
j=len(a)-1
while i<=j:
m=(i+j)//2
ans+=str(a[m])+""
if a[m]==key:
break
if a[m] i=m+1
elif a[m]>key:
j=m-1
print(ans)
执行该程序段后，变量ans的值不可能是 （　　）
A."853" B."857"
C."81510" D."81516"
A
√
随机生成key的值为7、14或21。ans连接二分查找过程中访问的元素，根据数组a的值可画出如图所示的二分查找判定树。当key=7时，查找的元素依次为8、5、7，故ans的值为"857"；当key=14时，查找的元素依次为8、15、10，故ans的值为"81510"；当key=21时，查找的元素依次为8、15、16，故ans的值为"81516"。
4.［2025嘉兴模拟］某二分查找算法的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表示二分查找过程中查找的元素个数减1，根据程序可画出如图所示的二分查找判定树，当key为24、27、30时，c的值为3。
5.［2025杭州模拟］某二分查找算法的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为查找次数，数组d中每个元素需要的查找次数为[2,3,1,3,2,3]。当n=2时，c=2+1+2=5；当n=3时，c=2+3=5；当n=4时，c=2+2=4；当n=5时，c=2+3=5。
C
√
6.有如下Python程序段：
import random
a=[1,3,5,7,9,11,13,15]
key=random.randint(1,8)*2
i,j=0,len(a)-1
s=0
while i<=j:
m=(i+j+1)//2
if a[m]==key:
break
if a[m]>key:
j=m-1
s-=1
else:
i=m+1
s+=1
print(s)
执行该程序段后，s的值可能有 （　　）
A.4种 B.5种 C.7种 D.8种
根据二分查找的过程画出如图所示二分查找判定树，key的值可能为2、4、6、8、10、12、14、16。往左查找时s值减1，往右查找时s值加1，可以得出在列表a中进行二分查找之后，s值有-2、-1、1、3共4种可能。
A
√
7.某小区停电，电工需排查线路故障。现将总线路均分为n个检测点，正常路段的检测值均为1，故障路段的检测值均为0，将每个检测点的检测值分别存入数组f中（如[1,1,1，1,0,0,0]表示第4～5个监测点之间有故障点，所以后面的路段检测值均为0）。为提高排查效率，采用二分查找的方式找出故障点所在位置。模拟该过程的部分Python程序如下：
i=0;j=n-1
cnt=0
while i<=j:
m=(i+j)//2
cnt=cnt+1
if f[m]!=0:
i=m+1
else:
j=m-1
若n的值为10，查找结束后cnt的值为4，则故障点所在位置可能是 （　　）
A.第2～3个检测点之间 B.第3～4个检测点之间
C.第5～6个检测点之间 D.第8～9个检测点之间
B
√
已知故障点所在位置即数组第一个0所在位置，每进行一次查找，cnt加1，故二分查找共进行4次。10个检测点根据二分查找可画出如图二叉树。
检测点值为0则向左查找，值为1则向右查找，即节点值为0有左子树，节点值为1有右子树，则度为2的节点值可能为0或1。叶子节点没有子树，无法判断节点值，则也有可能为0或1。cnt=4表示查找4次，即要查找的节点在第4层，分别为4、7、10。查找过程如表所示。
查找检测点（节点）
检测值
数组值
故障点所在位置
检测点4
0
1110000000
第3～4个检测点之间
1
1111000000
第4～5个检测点之间
检测点7
0
1111110000
第6～7个检测点之间
1
1111111000
第7～8个检测点之间
检测点10
0
1111111110
第9～10个检测点之间
1
1111111111
无故障点
执行该程序段后，输入任意key值，最终输出s的值不可能是 （　　）
A.[78,58,67,60]
B.[55,78,61,59]
C.[73,50,41,38]
D.[51,77,78,79]
8.有如下Python程序段：
'''随机产生包含10个整型元素的升序序列，依次存入列表a，代码略'''
i=0;j=9;s=[]
key=int(input())
while i<=j:
m=(i+j+1)//2
s.append(a[m])
if a[m]==key:
break
elif a[m]>key:
j=m-1
else:
i=m+1
print(s)
D
根据程序可画出如图所示的二分查找判定树，节点数据为列表a中元素的索引值。由于列表数据升序，故索引值越大元素值越大。选项D中被访问的元素为升序排列，说明查找过程一直向右查找，根据二叉树可知，一直向右查找不可能经过4个节点。
√
9.［2026强基联盟］有如下Python程序段：
import random
a=[2,3,4,4,4,8,8,9,10]
key=random.randint(1,10)
i,j=0,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"
print(s)
运行该程序段后，输出的结果不可能是 （　　）
A.LLL B.LRL C.RLR D.RRRL
C
该程序段使用二分查找算法在数组a中查找key，每次取中点m，若a[m]>=key则字符串s连接"L"，否则字符串s连接"R"。根据数组a可画出二分查找判定树如图所示。若key小于等于2，则输出结果为LLL。若key等于4，则输出结果为LRL。若key等于10，则输出结果为RRRL。若查找路径为4→8→8，说明key一定小于等于8，之后不可能再往右查找，即输出结果不可能是RLR。
√
10.［2025浙江A9协作体］有如下Python程序段：
import random
a=[10,20,28,36,36,54,68,92,98]
f=[0]*len(a)
key=2*random.randint(10,45)+1
i=0;j=len(a)-1
n=0
while i<=j:
m=(i+j)//2
f[m]=1
if key>a[m]:
i=m+1;n=n+1
else:
j=m-1;n=n-1
执行该程序段后，下列说法正确的是 （　　）
A.变量i的值可能为4
B.变量n的取值范围为[-3,3]
C.数组f中至少有3个元素值为1
D.数组f的值可能为[0,0,0,0,1,0,1,1,1]
C
根据程序可知，key是[21,91]范围内的奇数，可画出如图所示的二分查找判定树（因为10与98不在范围内，所以图中没有表示）。当i=j=m=3时，若向右查找，将会得到i=4，而a[3]=36，向右查找说明key>36，初始中点元素a[4]的值也为36，因此若key>36，一开始就会在右半边查找，不会查找到左半边的a[3]，故i的值不可能为4。当向右查找时，n的值累加1；向左查找时，n的值累减1，则n的取值范围为[-1,1]。列表f标记二分查找过程中查找到的元素，根据程序可知，当key等于a[m]时继续向左查找，则至少查找了3个元素。若f的值为[0,0,0,0,1,0,1,1,1]，表示查找路径为a[4]、a[6]、a[7]、a[8]，而key的最大值为91，不可能经过a[8]，故flag[8]的值不可能为1。
√
执行该程序段后，下列说法不正确的是（　　）
A.若输出的结果是“该数不存在”，则search函数被调用的次数最多为4次
B.若search函数被调用了2次，则key的值可能是3或30
C.将①处的代码改为“m=(L+R+1)//2”，程序运行的结果不会改变
D.若数组a中的元素为降序，则不能用此程序进行查找
11.有如下Python程序段：
def search(key,L,R):
if L>R:
return "该数不存在"
else:
m=(L+R)//2　#①
if a[m]==key:
return m
elif a[m]>key:
return search(key,L,m-1)
else:
return search(key,m+1,R)
a=[2,3,8,12,19,23,25,30,34,50]
key=int(input())
print(search(key,0,len(a)-1))
A
根据程序可画出如图所示的二分查找判定树，若输出的结果是“该数不存在”，则search函数被调用的次数最多为5次。
√
阅读下列材料，回答第12至13题：
　　马尔科夫链在人工智能中有许多的应用实例。例如，某竞猜活动，每局猜中与否的概率均为50%，猜中则赢得1积分，猜不中则输掉1积分。初始积分为A，竞猜持续进行，直到积分为0或达到预期积分B（A、B均为正整数，且B>A）时停止。此过程可以通过马尔科夫链分析，前2轮结果如图所示。
12.数组元素d[0]至d[6]保存了如图所示二叉树的中序遍历序列，有如下Python程序段：
i,j=0,6
key=A
while i<=j:
m=(i+j)//2
if key<=d[m]:
j=m-1
else:
i=m+1
print(i,j)
执行该程序段后，输出的结果是 （　　）
A.1 0 B.2 1
C.3 2 D.4 3
根据题图可知，数组d中存放的数据为[A-2,A-1,A,A,A,A+1,A+2]，二分查找的目标值key为A。观察代码可知，找到key后会继续向左查找，直到i>j时，查找结束。故最终i指向数组d中第一个大于等于key的元素位置，j指向i的前一个位置，即i的值为2，j的值为1。
√
B
13.［2025绍兴模拟］模拟竞猜过程的gambler函数定义如下：
from random import randint
def gambler(A,B):
if A==0:
return "lose"
if A>=B:
return "win"
p=[-1,1]
i=randint(0,1)　#生成整数0或1
return gambler(A+p[i],B)
执行语句v=gambler(5,13)，函数gambler被调用n次后程序结束，则n的值不可能是（　　）
A.6 B.7
C.8 D.9
函数调用次数对应马尔科夫链的层数，若函数返回“lose”，则最终参数A的值为0，0最早在第6层出现，即n至少调用6次，之后只可能在第8，10，12，…层出现；若函数返回“win”，则最终参数A的值为13，13最早在第9层出现，即n至少调用9次。故n的值不可能是7。
√
B
14.有一数组呈左右交替上升排序，即第一小的数字排列在数组的最左边，第二小的数字排列在数组的最右边，第三小的数字排列在数组的左边第二个，第四小的数字排列在数组的右边第二个……根据这样的规律依次排列。编写如下Python程序，在左右交替上升的数组中查找指定数据key：
def search(li,key):
i=0
n=len(li)-1
j=　　　①　　　1
flag=False
while i<=j and not flag:
m=(i+j)//2
if key==li[m]:
flag=True
elif key j=m-1
else:
i=　　　②　　　1
if not flag and j>=0:
m=　　　③　　　1
if key==li[m]:
flag=True
if flag:
print(f"数组元素li[{m}]即是查找的元素")
else:
print("查找失败")
n//2
m+1
n-j
请回答下列问题：
（1）下列是左右交替上升数组的是　　　 　（单选）。
A.[1,3,5,7,8,9,6,4,2]
B.[2,8,15,17,33,27,23,10,5]
C.[3,12,22,77,92,35,15,7]
D.[78,54,24,3,15,37,62]
（2）利用上述程序在左右交替上升数组[1,5,9,13,15,11,7,3]中查找数据15，则程序输出的结果是　　　　　　　。
（3）请在画线处填入合适的代码。
√
C
数组元素li[4]即是查找的元素
（1）只有选项C中的数组符合左右交替上升排序的规律。　（2）左右交替上升数组是[1,5,9,13,15,11,7,3]，其中数字15所在的位置是下标为4的位置，故程序运行后输出：数组元素li[4]即是查找的元素。　（3）①处表示j的初始值，已知数组呈左右交替上升的规律，数组中的值先升序，再降序，故只能对一半的数组进行二分查找，此处j的初始值为n//2。②处是对i的重新赋值，i表示的是左边界，此处key的值大于等于li[m]，则左边界移动到m的右边一位，故填入代码为m+1。③处由于数组是左右交替上升的，故当左半边的值与key不相等时，需要对数组右半边进行查找，右半边的数据呈降序排序，左半边的位置m，映射到右半边即是n-j。

展开更多......

收起↑