资源简介

(共31张PPT)
课时35 二分查找与最值
一、二分查找
1. 二分查找的定义：二分查找又称折半查找、对分查找。它是一种效率很高的查找方法，但是被查找的数据序列必须是　　　　的。
2. 二分查找的基本方法。
（1）首先确定序列有序，例如递增数组 d。
（2）在查找范围(i,j)内，可以利用数据的有序性，仅取范围内的中间值比较，而不必逐个地进行查找。
①确定该区间的　　　　位置：m= (i+j)/2」（m 表示小于等于(i+j)/2 的最大整数）。
②将查找键 key 与 d[m]进行比较，结果必然是如下三种情况之一。
有序
情况 说明 相应操作
keykey=d[m] 找到了需要的数据 查找结束
key>d[m] 查找键大于中点d[m]的数据 因为数组d的数据递增，可以确定在(i,m)内不可能存在值为key的数据，所以只需在新的范围(m+1,j)中继续查找
中点
1. 若用一个列表 a 来存放升序的元素序列，用 i 表
示查找范围起始位置的下标，j 表示终止位置的下标，
m 表示中间位置元素的下标。假设查找键 key=12，二
分查找的过程如图所示。
二、二分查找的过程
2. 如图所示是在规模为 n 的数组 d 中进行二分查找的流程图。
二分查找的缺点是要求查找数据必须有序，当查找数据量大时，二分查找的查找效率较高，无论是否找到，最多进行 log2N」+1 次查找，其时间复杂度为 O(log2n)。
三、二分查找的算法效率
1.经典二分查找算法的实现。
key=int(input("key="))
a=[6,12,15,18,22,25,28,35,46,58,60]
flag=False
i=0
j=len(a)-1
while i<=j:
m=(i+j)//2
if key==a[m]:
flag=True
b=m
break
elif keyj=m-1
四、二分查找的 Python 实现
else: #到右边去找
i=m+1
if flag==True:
print("查找成功！第"+str(b)+"个")
else:
print("没有找到！")
2.二分查找算法的递归实现。
def bsearch(s,array):
if len(array)==0:
print("未找到！")
return False
mid=(len(array)-1)//2
if array[mid]==s:
print("找到了！")
return True
elif sreturn bsearch(s,array[:mid])
else:
return bsearch(s,array[mid+1:])
key=12
d=[6,12,15,18,22,25,28,35,46,58,60]
bsearch(key,d)
1. 若要查找大于等于 key 的最小值，应设置查找条件为当 a[m]>=key 时，设置 j=m-1 继续往左查找，否则设置 i=m+1 继续往右查找。当循环结束时，i==j+1，此时 i 指向的元素即大于等于 key 的第一个元素。
2. 若要查找小于等于 key 的最大值，应设置查找条件为当 a[m]<=key 时，设置 i=m+1 继续往右查找，否则设置 j=m-1 继续往左查找。当循环结束时，i==j+1，此时 j 指向的元素即小于等于 key 的最后一个元素。
五、二分查找与最值
典例 1 某 7 位同学的身高（单位：cm）从高到低依次为 178，177，175，172，170，165，162。用二分查找算法查找 178，依次被访问到的数据是（　　）
A.178
B.172，175，178
C.172，177，178
D.172，175，177，178
C
√
题型导向一　二分查找的过程
胜券点拨1
明考向 本题主要考查二分查找的过程
审关键 每次取范围内的中点查找
考场思 维快闪 将7个数据从0到6依次进行编号，第一次访问编号3，即数据172，172<178，故往左半部分查找（注意这里数据序列是降序排序的）；第二次访问编号1，即数据177，177<178，则继续往左查找；第三次访问编号0，即数据178，查找完成
典例 2 ［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
√
胜券点拨2
明考向 本题主要考查流程图和二分查找
审关键 变量c记录向右查找的次数
考场思 维快闪 符号“ 」”表示向下取整，该流程图执行过程如表所示
i j m c i≤j a[m]=key a[m]0 6 3 0 Y N Y
4 6 5 1 Y Y，输出m和c —
执行该程序段后，下列说法正确的是 （　　）
A.无论 key 的值是否在列表 d 中出现，输出 i 的值
一定比 j 大
B.当输入 key 的值大于 d[0]时，输出 j 的值为 0
C.当输入 key 的值为 40 时，输出 m 的值为 5
D.当输入 key 的值为 40 时，输出 n 的值为 3
典例 3 某二分查找算法的 Python 程序段如下：
d=[88,77,53,47,39,28]
key=int(input("key="))
i=0
j=len(d)-1
n=0
while i<=j:
m=(i+j)//2
n+=1
if d[m]==key:
break
if key>d[m]:
j=m-1
else:
i=m+1
print(i,j,m,n)
D
√
题型导向二　二分查找的 Python 实现
胜券点拨3
明考向 本题考查二分查找算法的程序实现
审关键 二分查找算法实现过程中的语句作用
考场思 维快闪 该程序段实现二分查找，当a[m]与key相等时退出循环，故输出i的值不一定大于j。当输入key的值大于d[0]时，输出j的值为-1。当输入key的值为40时，输出i、j、m、n的值分别是4、3、3、3
典例 4 ［2025精诚联盟］定义如下函数：
def find(i,j,key):
if i>j:
return -1
else:
m=(i+j)//2
if key==a[m]:
return m
elif keyreturn find(i,m-1,key)
else:
return find(m+1,j,key)
若 a=[1,3,5,6,7,9,11,12,15]，则调用函数 find(0,8,5)后，下列说法不正确的是 （　　）
A.函数 find 共被调用 3 次
B.函数返回值为 2
C.语句“elif keyD.该函数的时间复杂度为 O(n2)
D
√
胜券点拨4
明考向 本题主要考查二分查找算法的递归实现
审关键 二分查找、递归
考场思 维快闪 函数find(i,j,key)采用递归的方式二分查找元素key，查找范围为i~j，中点为m，当中点元素等于key时，函数返回值为m；当中点元素大于key时，则递归调用find(i,m-1,key)继续在左半边二分查找；当中点元素小于key时，则递归调用find(m+1,j,key)继续在右半边二分查找。若a=[1,3,5,6,7,9,11,12,15]，则函数调用过程为find(0,8,5)→find(0,3,5)→find(2,3,5)，最终返回值为2，该函数的时间复杂度为O(log2n)
典例5　［2025.6浙江选考］定义如下函数，返回key在列表data中的下标，若key不存在，则返回-1。
def bsearch(data,key):
i,j=0,len(data)-1
while i<=j:
m=(i+j)//2
for k in range(m-1,m+2):
if i<=k<=j and data[k]==key:
return k
if data[m]i=m+2
else:
j=m-2
return -1
如果调用函数返回结果不正确，则data可能是 （　　）
A.[16,19,18,22,20,29,25]
B.[16,19,20,18,22,25,29]
C.[18,16,19,20,22,29,25]
D.[18,16,20,19,25,22,29]
B
√
胜券点拨5
明考向 本题主要考查二分查找的变式
审关键 查找的过程
考场思维快闪 该程序是二分查找的变式，程序在运行时，检查中间位置m和相邻位置，即m-1、m、m+1三个位置，若找到key，则返回下标，否则根据比较结果向左、右方向移动指针（步长为2）。这种跳跃式查找可能导致某些数据被跳过，从而无法找到，因此data需要满足：任何key的潜在位置必须能被m-1、m或m+1覆盖。选项B，若key=19，则程序无法找到key，返回-1
典例 6 某二分查找算法用于查找非降序序列 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)
画线处有如下可选代码：
①L画线处应填入的正确代码依次为 （　　）
A.①③ B.①④ C.②③ D.②④
D
√
题型导向三　二分查找与最值
胜券点拨6
明考向 本题考查二分查找与最值
审关键 小于等于key的最后一个元素
考场思 维快闪 （1）在二分查找算法中，条件“L<=R”用于控制循环的边界，确保算法能够正确地遍历数组或列表的一部分，直到找到目标元素或确定目标元素不存在为止。（2）已知arr为非降序序列，当中间位置mid的元素小于等于key时，继续向右查找，故填入代码为arr[mid]<=key
典例 7 ［2025 浙江名校协作体］有如下 Python 程序段：
a=[13,23,34,44,55,67,78,80,85,90]
i=0;j=9
s=[-1]*4;top=-1
n=0
key=int(input())
while i<=j:
m=(i+j)//2
if a[m]>=key:
j=m-1;n+=1
top+=1;s[top]=m
else:
i=m+1;n-=1
if top!=-1:
top-=1
下列说法正确的是 （　　）
A.i的值不一定等于 j+1 B.n 的值最小为-3，最大为 4
C.输入任意 key 的值，top 的最大值为 3 D.若输入 key 的值为 67，则 s 的值为[7,5,-1,-1]
D
√
胜券点拨7
明考向 本题考查二分查找与最值、栈
审关键 查找条件
考场思维快闪 A 二分查找结束时，i的值一定等于j+1
B 向左查找时，n的值累加1，向右查找时，n的值累减1，故n的值最小为-4，最大为3
C 在向左查找的过程中，将m值入栈s，在向右查找的过程中，若栈s不为空，则将当前栈顶元素出栈，最多向左查找3次，故top的最大值为2
D 若输入key的值为67，第1次查找m=4，a[4]<67，则i=5；第2次查找m=7，a[7]>67，则j=6，同时7入栈s；第3次查找m=5，a[5]=67，则j=4，同时5入栈s；此时i>j，查找结束。故最终s的值为[7,5,-1,-1]
查找方式 顺序查找 二分查找
被查找序列 顺序无要求 要求有序
数据类型 无要求 数据类型相同，且可进行比较
查找效率 最好的情况查找1次，最差的情况查找n次，平均查找次数是（n+1）/2，时间复杂度是O（n） 时间复杂度是O（log2n），查找次数不超过判定树的高度，即最多为 log2n」+1次
通法一　二分查找与顺序查找辨析
项目 顺序查找 二分查找
核心代码 （设升序序列为lis，待查找数据为key） for i in range(len(lis)):　#① if key==lis[i]:　#② print("查找成功") break i=0　#左边界
j=len(lis)-1　#右边界
while i<=j:　#范围合理
m=(i+j)//2　#①
if lis[m]==key:
print("查找成功")
break
if keyj=m-1
else:
i=m+1
重点分析 ①顺序遍历序列lis ②比较遍历到的元素与key ①一般情况下给m赋值为(i+j)//2，但有部分情况下将m赋值为(i+j+1)//2，即当i+j的值为奇数时，两种情况比较的元素不同，但是实现的效果是一样的
②要注意序列的升序或降序，程序中的lis是升序排序的，所以当keylis[m]时修改右边界，此处注意辨析
通法二　顺序查找与二分查找的 Python 编程通法
查找内容 小于等于key的最大值 大于等于key的最小值
程序 a=[5,6,7,7,8,9,10] key=int(input()) i,j=0,len(a)-1 while i<=j: m=(i+j)//2 if a[m]<=key: i=m+1 else: j=m-1 print(i,j,m) a=[5,6,7,7,8,9,10]
key=int(input())
i,j=0,len(a)-1
while i<=j:
m=(i+j)//2
if a[m]>=key:
j=m-1
else:
i=m+1
print(i,j,m)
输出结果 ①输入key的值是：7 输出的结果是：4 3 4 ②输入key的值是：12 输出的结果是：7 6 6 j指向的元素即小于等于key的最后一个元素 ①输入key的值是：7
输出的结果是：2 1 2
②输入key的值是：4
输出的结果是：0 -1 0
i指向的元素即大于等于key的第一个元素
通法三　最值的查找
1.对长度为7的有序数组做二分查找，若查找失败，则至多比较的次数是 （　　）
A.7
B.5
C.3
D.1
7个元素的查找最多比较int(log27)+1=3次。
一、二分查找的过程
C
√
2.定义如下函数：
def search(lst,i,j,key):
if i>j:
return -1
m=(i+j)//2
if lst[m]>key:
return search(lst,i,m-1,key)
elif lst[m]return search(lst,m+1,j,key)
else:
return m
若列表lst为[12,31,47,50,55,55,71,76]，则执行语句search(lst,0,7,51)后，该函数被调用的次数为 （　　）
A.1 B.2 C.3 D.4
该函数实现二分查找算法，需要调用4次函数，调用过程为：search(lst,0,7,51)→search(lst,4,7,51)→search(lst,4,4,51)→search(lst,4,3,51)=-1。
D
√
二、二分查找的Python实现
3.有如下Python程序段：
a=[19,25,29,30,33,36,78,87,96,100]
ans=[]
i=0;j=9
key=int(input("请输入待查数据："))
flag=False
while i<=j and not flag:
m=(i+j+1)//2
if a[m]==key:
flag=True
elif a[m]>key:
j=m-1
else:
i=m+1
ans.append(a[m])
print(ans)
执行该程序段后，若输入key的值为25，则输出的结果是 （　　）
A.[33] B.[33,25]
C.[36,29] D.[36,29,25]
D
√
该程序段实现使用二分查找算法在数组a中查找key，并使用数组ans记录每次查找到的元素。若输入key的值为25，初始i=0，j=9，m=5，a[5]=36>25，ans=[36]；继续向左查找，j=4，m=2，a[2]=29>25，ans=[36,29]；继续向左查找，j=1，m=1，a[1]=25，查找结束，ans=[36,29,25]。
4.某二分查找算法用于查找非降序序列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+1)//2
if 　　　（2）　　　:
L=mid+1
else:
R=mid-1
print(　　　（3）　　　)
画线（1）（2）（3）处有如下可选语句：
①L画线处应填入的代码依次为 （　　）
A.①③⑤ B.①④⑥
C.②③⑤ D.②④⑥
D
√
二分查找的左右边界为L和R，则当L<=R时，继续查找。要查找非降序序列arr中小于等于key的最后一个元素位置，则当中点元素等于key时，应继续向右查找，即当arr[mid]<=key时，执行“L=mid+1”。循环结束时，R指向小于等于key的最后一个元素位置。
三、二分查找与最值
5.［2025强基联盟］某二分查找算法的Python程序段如下：
key=[12,18,27]
a=[12,18,18,27,27,45]
ans=0
for k in key:
c=0
i=0
j=len(a)-1
while i<=j:
m=(i+j)//2
c+=1
if a[m]<=k:
i=m+1
else:
j=m-1
ans+=c
print(ans)
执行该程序段后，ans的值是 （　　）
A.8 B.5 C.7 D.9
该程序段使用二分查找算法在数组a中查找数组key中的元素k，当中点元素a[m]等于k时继续向右查找，c统计查找次数，ans累加查找每个k的查找次数。当查找12时，查找次数为3；当查找18时，查找次数为3；当查找27时，查找次数为3。故ans的值为9。
D
√
6.有如下Python程序段：
a=[100,90,15,40,72,65,32,81,6]
b=[8,2,6,3,5,4,7,1,0]
i=0;j=len(a)-1
c=0;key=72
while i<=j:
m=(i+j)//2
if a[b[m]]==key:
break
elif a[b[m]]i=m+1
else:
j=m-1
c+=1
执行该程序段后，变量c的值为 （　　）
A.4 B.3 C.2 D.1
该程序段通过二分查找算法在数组a中查找数据key，每次取数组b的中点元素作为数组a的索引。初始i=0，j=8，m=4，b[4]=5，a[5]=65key，c=2；继续向左查找，i=5，j=5，m=5，b[5]=4，a[4]=72=key，退出循环，c不会累加1，故最终c的值为2。
C
√
7.某次学生测试成绩从高到低存储在数组a中。输入key值，查找大于等于key值人数的Python程序段如下：
a=[98,…,85,85,85,85,…,50]
key=int(input("请输入要查找的数据："))
i=0;j=len(a)-1
while i<=j:
m=(i+j)//2
if 　　　（1）　　　:
i=m+1
else:
j=m-1
print("大于等于key值的人数为：",　　　（2）　　　)
画线（1）（2）处有如下可选语句：
①key<=a[m]　②key则应填入的正确语句依次为 (　　)
A.①③ B.①④
C.②③ D.②④
A
由于数组a中的元素降序排序，所有大于等于key的元素都集中在数组左侧。使用二分查找寻找第一个满足a[p]√
else:
left=mid+1
return -1
loss=[95,87,65,48,21,15,20,28]
#结果为15
peak_value=find_peak(loss)
下列关于该算法的说法，正确的是 （　　）
A.该算法的时间复杂度是O(nlog2n)
B.该算法在单调递减的情况下也能正常运行
C.若连续多轮损失函数的值都是最优解，则该算法可以找到第一次出现最优解的轮次
D.在本例中，函数返回时left和right的值分别是4和7
8.［2025镇海中学检测］在图片分类任务训练神经网络时，损失函数的值（模型错误预测程度）通常会在训练开始阶段时较高，随着训练轮数的增加而逐渐下降，直到达到最小值（即最优解），但继续训练可能会导致出现过拟合现象（此时损失函数的值反而增高），小明使用如下算法确定效果最好时损失函数的值。
def find_peak(arr):
left=0
right=len(arr)-1
while left<=right:
mid=(left+right)//2
if arr[mid]<=arr[mid-1] and arr[mid]<=arr[mid+1]:
return arr[mid]
elif arr[mid]>arr[mid-1]:
right=mid-1
D
该算法的时间复杂度是O(log2n)。若数组arr单调递减，将会一直执行“left=mid+1”，当mid为最后一个元素索引时，arr[mid+1]会越界。若连续多轮损失函数的值都是最优解，则找到的不一定是第一次出现的。初始left=0，right=7，mid=3，a[mid]>a[mid+1]；继续向右查找，left=4，right=7，mid=5，满足arr[mid]<=arr[mid-1] and arr[mid]<=arr[mid+1]，返回15。
√
9.实现查询功能的Python程
序段如下，程序输出效果如图所示。
姓名 班级 总分
程二 三（4） 709
赵八 三（2） 709
项时 三（5） 689
李三 三（1） 608
曾九 三（1） 608
陈七 三（1） 606
王一 三（5） 598
吴四 三（1） 598
夏五 三（3） 598
张六 三（3） 409
输入需要查找的分数：598
['王一', '三（5）', '598']
['吴四', '三（1）', '598']
['夏五', '三（3）', '598']
'''将文件cj.csv中的有序数据存入数组a中，并输出，代码略'''
key=int(input("输入需要查找的分数："))
i=1
j=len(a)-1
while i<=j:
　　　①　　　1
if 　　　②　　　:
j=m-1
else:
i=m+1
while 　　　③　　　:
print(a[i])
i=i+1
画线处应填入的代码是 （　　）
A.①m=(i+j+1)//2　②a[m][2]③a[i][2]==key
B.①m=(i+j)//2　②a[m][2]<=key　
③a[j][2]==key
C.①m=(i+j+1)//2　②a[m][2]<=key　
③a[m][2]==key
D.①m=(i+j)//2　②a[m][2]<=key　
③a[i][2]==key
D
√
该程序段通过二分查找查找第一个大于等于key的元素位置，因此当中点元素等于key时，将继续向左查找。第1个while循环结束后，i指向第一个大于等于key的所在位置，第2个while循环从i开始，逐个遍历，将所有满足条件的元素输出。
10.已知数组元素由正数、负数或0构成，且无重复数据。编写Python程序,实现在一个升序排列的数组中查找绝对值最小的元素。若绝对值相等，则输出较小数。例如：数组为[27,17,16,-5,13,8,2,-9]，该数组中绝对值最小的数是2。程序运行结果如图所示。
请回答下列问题：
（1）若输入数组为[3,-6,5,1,-1,-4]，则该数组中绝对值最小的元素是
　　　　　　　。
[-9,-5,2,8,13,16,17,27]
绝对值最小的元素是：2
>>>
-1
（2）实现上述功能的Python程序如下，请在画线处填入合适的代码。
'''产生n个由正数、负数或0构成的元素（无重复），存储在数组a中，并升序排列，代码略'''
def dmin(x,y):
min=x
if abs(x)>abs(y):
min=y
return min
#查找绝对值最小的数
i=0
j=n-1
flag=False
while 　　　①　　　:
m=(i+j)//2
if a[m]==0:
flag=True
absmin=a[m]
break
elif a[m]>0:
if 　　　②　　　:
j=m-1
else:
flag=True
absmin=dmin(a[m-1],a[m])
else:
if a[m+1]<0:
i=m+1
else:
flag=True
　　　③　　　1
print("绝对值最小的元素是："+
str(absmin))
flag==False　或　i<=j and flag==False　或其他等价答案
a[m]>abs(a[m-1])　或　a[m-1]>0　或其他等价答案
absmin=dmin(a[m],a[m+1])（注：a[m],a[m+1]顺序不可交换）
（1）根据题目要求，将序列[3,-6,5,1,-1,-4]排序后得到[-6,-4,-1,1,3,5]，-1和1绝对值相等，较小的为-1。　（2）由题干中“数组元素由正数、负数或0构成”，故绝对值最小值为0或正负交替边界，所以不为正负交替时进行二分查找，正负交替时比较正负两边绝对值大小，当a[m]>0时，若a[m-1]<0，即为正负交替时，则只需比较a[m-1]与a[m]；当a[m]<0时，若a[m+1]<0则继续二分查找，若a[m+1]>0，即为正负交替时，则只需比较a[m]与a[m+1]。①处是继续查找的条件，当查找成功时结束查找，所以当查找成功时，逻辑值flag均会赋值为True，故填入代码为flag==False。②处由于绝对值最小数只能在0或者正负交替时产生且一定存在，由于序列升序，所以当a[m]>0，且a[m-1]>0时继续二分查找，故填入代码为a[m-1]>0。③处是当a[m]<0且a[m+1]>0时，即为正负交替时，只需比较a[m]与a[m+1]确定最小值，故填入代码为absmin=dmin(a[m],a[m+1])。

展开更多......

收起↑