资源简介

(共75张PPT)
课时5　二分查找
第五章　数据结构与算法
1.通过实例分析，理解顺序查找的基本思想，掌握使用二分查找的一般方法。
2.能根据不同的应用场景，选择合适的数据结构，能灵活使用二分查找算法编写程序。
目 录
CONTENTS
知识梳理
01
例题精析
02
随堂检测
03
巩固与提升
04
知识梳理
1
1.二分查找(Binary Search)
二分查找又称对分查找或折半查找。
二分查找是指在有序的数据序列中，首先将要查找的数据元素与数组的____________元素进行比较，如果相等，则查找成功并退出查找；否则，根据数组元素的有序性，确定新的____________(在数组的前半部分还是在后半部分)；在确定了新的查找范围后，重复进行以上操作，直到找到或查找结束为止。
①二分查找的前提条件是待查找的数据序列必须有序。
②“未找到”是指当前查找区间不存在，即区间左端点大于右端点。
中间位置
查找范围
2.二分查找的算法框架
说明：要查找的目标数据元素为key，待查找的数据元素存放在数组d中。
i、j分别为查找区间的起点位置和终点位置，m为查找区间的中间位置，n为数据元素个数。
i＝0
j＝n－1
while i<＝j：
#计算中点位置m
#比较key与d[m]，并做相应处理
#若i>j，则表示未找到
3.二分查找的程序实现
·设要查找的数据是key，待查找的数据元素存放在数组d中，并已按升序排序。
·输出查找结果，若找到则输出信息“找到！位置为：X”，否则输出“查无此数！”
·输出查找次数c。
二分查找主要代码如下(以升序为例)：
输入key的值
c＝0　　　　　　　#记录查找次数
find＝False　　　　#设置find的初值
i＝0　　　　　　　#区间左端点位置
j＝n－1　　　　　 #区间右端点位置
while _____________________：　#还未找完并且还未找到，则继续查找
c＝c＋1　　　　#查找次数记数
m＝____________　 #计算中点位置m，等价于m＝int((i＋j)/2)
if key＝＝d[m]：　 #找到目标元素，并进行相应处理
find＝True
print(m)
if key>d[m]：　　#表示要查找的元素比中间位置上的元素大时
i＝m＋1　　　#调整区间左端点
i<＝j and not find
(i＋j)∥2
else：　　　　　
j＝m－1　　　#调整区间右端点
if find＝＝False：
print(″查无此数！″)
print(″查找次数为：″，c)
例题精析
2
例1 有如下两组数据：
A
①1，2，3，4，5，6，7，8，9
②3，4，5，2，1，8，7，6，9
A.①②都可以直接使用二分查找
B.①②都可以直接使用顺序查找
C.①可以直接使用顺序查找，也可以直接使用二分查找
D.②可以直接使用顺序查找，但不能直接使用二分查找
解析　本题主要考查的是使用顺序查找和对分查找的适用条件。顺序查找对待查找的数据没有要求，而二分查找的前提是数据必须有序。①中数据有序，②中数据无序，①中数据顺序查找和二分查找均可以直接使用，②中数据只能使用顺序查找，若要使用二分查找，则先对②中数据进行排序操作。因此，不正确的是A，答案为A。
变式训练　分别使用顺序查找算法和二分查找算法在数据序列“5，6，10，13，15，20，21，26，30”中查找数据10，下列关于查找的次数的说法中正确的是(　　)
A.顺序查找2次，二分查找3次 B.顺序查找3次，二分查找2次
C.顺序查找3次，二分查找3次 D.顺序查找3次，二分查找4次
解析　本题主要考查的是顺序查找和二分查找的算法思想。数据10是数据序列中第3个元素，因此使用顺序查找时，共查找次数为3次，使用二分查找时，依次被访问的数据为15、6、10，即二分查找的次数也为3次。因此，答案为C。
C
例2 在列表lista中存储的数据依次为：88，78，70，65，60，55，51，45，39，28。现使用二分查找算法在列表lista中查找数据51，共需查找的次数为(　　)
A.1次 B.2次 C.3次 D.4次
解析　本题主要考查的是二分查找的查找过程。第一次找到的索引号为4的数据(60)，因为51<60，因此向右查找，第二次找到索引号为7的数据(45)，因为51>45，因此向左查找，第三次找到索引号为5的数据(55)，因为51<55，因此向右查找，第四次找到索引号为6的数据(51)，找到要找的数据后结束查找，因此共查找了4次，答案为D。
D
变式训练　有100个英语单词已按升序排序并存储在列表listb中，现要使用二分查找算法在列表listb中查找某个单词，则最多的查找次数为(　　)
A.5次 B.6次 C.7次 D.8次
解析　本题主要考查的是计算二分查找的查找次数。N个数据，使用二分查找，查找次数最多为log2(n)取整加1，现共有100个单词，因此最多次数为7次，答案为C。
C
例3 某二分查找算法的Python程序段如下：
n＝0; flag＝True
key＝int(input(″输入要查找的数：″))
i，j＝0，9
while i<＝j and flag：
m＝(i＋j)∥2
if a[m]＝＝key：
flag＝False
elif a[m]i＝m＋1
n＝n＋1
else：
j＝m－1
n－＝1
解析　本题主要考查二分查找算法。用二叉搜索树画出各个元素的搜索顺序，图中各个左子树方向可以让n自减，右子树方向可以让n自增。
B
A选项，若key＝25，则从节点23的右侧出循环，此时m、n的值是3、2，同理key＝45, m、n的值是8、2，key＝60，m、n的值是9、2。key＝34，m、n的值是6、1。
变式训练　某二分查找算法的Python程序段如下：
b＝[98，86，81，77，66，60，48，20]
key＝int(input(″key＝″))
i，j＝0，len(b)－1
s＝″″
while i<＝j：
m＝(i＋j)∥2
if b[m]＝＝key：
s＝s＋″M″
break
if keyi＝m＋1
s＝s＋″R″
else：
j＝m－1
s＝s＋″L″
print(s)
程序执行时，输入key的值为55，则输出的结果为(　　)
A.RRL B.RLR C.RRLR D.RRLM
解析　本题主要考查的是二分查找时的方向问题。本题的功能是求使用二分查找在降序序列中查找数据55的过程，如果找到，则记为“M”，如果要查找的数据在序列的右边区间中，则记为“R”，否则记录为“L”。因此，答案为A。
A
例4 有如下 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[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。
A
变式训练　有如下 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
随堂检测
3
A.使用顺序查找算法查找数据10，共查找了3次
B.使用二分查找算法查找数据10，共查找了3次
C.使用顺序查找算法查找数据25，共查找了7次
D.使用二分查找算法查找数据25，共查找了3次
D
解析　本题主要考查的是顺序查找和二分查找算法思想。使用二分查找算法查找数据25，需要的查找次数为4次，因此D选项不正确，答案为D。
2.在7个有序的数列“a1，a2，a3，a4，a5，a6，a7”中，采用二分查找法查找数值key，依次需要进行比较的数据可能是(　　)
A.a4 B.a4，a6，a2
C.a4，a2，a5 D.a4，a6，a5，a7
A
解析　本题考查二分查找的算法思想。第1次查找的是最中间的节点a4，因此A选项正确。B选项a2比a4小，查找到a6后，不可再去找a2。C选项a5比a4大，也不可能。D选项第3次查找，要么a5或a7，不可能2个数同时被查找到。
3.某对分查找算法的Python程序段如下：
a＝[85，74，70，65，54，36，30，28，26，12]
t＝″″
i，j＝0，9
key＝30
f＝False
while i<＝j and not f：
m＝(i＋j)∥2
t＋＝str(m)
if a[m]＝＝key：
f＝True
elif a[m]>key：
i＝m＋1
t＝t＋″→″
else：
j＝m－1
t＝t＋″←″
C
执行该程序段，变量t的值是(　　)
A.″4→7←5→″ B.″4→7←5→6→″
C.″4→7←5→6″ D.″4→7→5→6→″
解析　本题主要考查的是二分查找的程序实现。本题的功能是在一个降序数列中查找key的过程，记录每次访问的元素，并标识查找的方向(向右→或向左←)。在数列中查找30的过程中，第一次查找时，m＝4，t＝“4”，因为a[4]＝54>key，因此向右查找，i＝5，t＝“4→”；第二次查找时，m＝7，t＝“4→7”， 因为a[7]＝28key，因此向右查找，i＝6，t＝“4→7←5→”；第四次查找时，m＝6，t＝“4→7←5→6”， 因为a[6]＝＝key，因此查找结束，故答案为C。
4.某二分查找算法的Python程序段如下：
a＝[125，117，115，108，102，95，88，63，51，36]
key＝108
i，j＝0，len(a)－1
ss＝″″
while i<＝j：
m＝int((i＋j)/2＋0.5)
ss＝ss＋str(m)
if key＝＝a[m]：
break
if keyC
i＝m＋1
ss＝ss＋″>>″
else：
j＝m－1
ss＝ss＋″<<″
print(ss)
执行该程序段，输出的内容为(　　)
A.4<<1>>2>>3 　 B.5<<2<<4>>3
C.5<<2>>4<<3 D.5<<2>>4>>3
解析　本题主要考查的是二分查找的变式。本题中将中间位置m的计算公式修改为m＝int((i＋j)/2＋0.5)，即在偶数个数的区间中，找到的m为中间靠右的位置，因此，在查找数据108的过程中，依次访问的元素位置为5、2、4、3，注意左右方向的表示。查找结束时，字符串ss的内容为5<<2>>4<<3，答案为C。
5.某对分查找算法的Python程序段如下：
n＝len(a)
f＝[0]*n
key＝int(input(″输入要查找的数：″))
i，j＝0，n－1
while i<＝j：
m＝(i＋j)∥2
f[m]＝1
if a[m]>＝key：
j＝m－1
else：
i＝m＋1
D
A.5 B.8 C.14 D.15
解析　本题考查对分查找的次数。本题为对分查找，数组f标记查找过的下标，若为3，表明共查找了3次。而该题中，查找找到不退出，退出的唯一条件是j。我们可以根据选项n的数量画出二叉判定树，若不存在从第三层结束的可能，就是不可能选项。
6.有如下Python程序段：
key＝int(input())
i＝0；j＝len(a)－1
s＝″″
while i<＝j：
　　m＝(i＋j＋1)∥2
　　if key＝＝a[m]：
break
　　if keyj＝m－1
　　else：
i＝m＋1
　　s＋＝str(a[m])＋″，″
print(s[：－1])
B
若数组元素a的值为[6，15，18，20，25，30，35，38，41，46]，输入正整数key值，执行该程序段，输出的值可能是(　　)
A.30，20 B.30，41，38
C.25，15，6 D.25，38，41
解析　根据二分查找算法画出对应的二叉树为 ，
可以得到遍历的路径。
7.有如下 Python 程序：
import random
a＝[15，18，25，34，38，40，55，61，80，85]
key＝random.randint(15，55)
f＝[0]*10
i＝0；j＝len(a)－1
while i<＝j：
　　m＝(i＋j＋1)∥2
　　if a[m]>key：
　j＝m－1
　else：
　if a[m]%5＝＝0：
　　　f[m]＝1
　i＝m＋1
D
执行该程序段后，列表 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。
8.有如下 Python 程序段：
def binSearch(i，j，key)：
　if i>j：
　return－1
　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))
B
解析　本题考查递归法求二分查找，找到后返回中间位置，没有找到，累加找过的位置m。用索引位置画出二叉树为 ，没有一条分支节点和为8。
4
巩固与提升
基础巩固
能力提升
A.使用对分查找查找数据60，共查找了3次
B.使用顺序查找查找数据60，共查找了1次
C.使用对分查找查找数据35，共查找了3次
D.使用顺序查找查找数据35，共查找了8次
C
解析　本题主要考查的是顺序查找和二分查找算法思想。使用二分查找算法查找数据35，需要的查找次数为4次，因此C选项不正确，答案为C。
2.列表数组a中存储了6个元素，依次为105、110、112、118、120、126，若采用二分查找算法在该列表中查找数据126，则在查找126的过程中依次被访问到的元素为(　　)
A.118、126 B.118、120、126
C.112、120、126 D.112、120、118、126
C
解析　本题主要考查的是二分查找的算法思想。使用二分查找算法查找数据126的过程中，首先被访问到的元素为112，第二次被访问到的元素为120，第三次被访问到的元素为126，因此，答案为C。
3.某二分查找算法的Python程序段如下：
list1＝[2，6，8，9，12，15，18，20]
key＝int(input(″请输入待查找的数据：″))
s＝″″
c，i，j＝0，0，7
while i<＝j：
c＋＝1
m＝(i＋j)∥2
if list1[m]＝＝key：
　　s＝s＋str(m)
break
if list1[m]>key：
j＝m－1
else：
i＝m＋1
s＝s＋str(m)＋″→″
print(s)
D
执行该程序段，输入待查找的数key为12，则输出的结果是(　　)
A.4→5→ B.4→6→5 C.3→5→4→ D.3→5→4
解析　本题主要考查的是二分查找的程序实现。使用二分查找算法查找数据12的过程中，第一次访问的是索引号为3的元素9，第二次访问的是索引号为5的元素15，第三次访问的是索引号为4的元素12，查找结束，因此，答案为D。
4.某二分查找算法的Python程序段如下：
list1＝['Carrot'，'Celery'，'Garlic'，'Lettuce', 'Mooli', 'Onion'，'Potato'，'Tomato']
key＝list1[2]
left，right＝0，len(list1)－1
c＝0
while left<＝right：
m＝(left＋right)∥2
c＝c＋1
if list1[m]>key：
right＝m－1
else：
left＝m＋1
print(list1[left])
B
程序执行后，下列说法正确的是(　　)
A.变量c的值为4
B.程序输出的结果为Lettuce
C.变量left的值为2
D.变量right的值为3
解析　本题主要考查的是二分查找的变式。本题的功能是在列表list1中查找第1个大于key的元素。c表示共查找的次数，共查找了3次，因此A选项错误；查找结束时，left＝3，right＝2，因此CD选项错误；查找结束时，因为left＝3，因此程序输出的结果为Lettuce，答案为B。
5.某二分查找算法的Python程序段如下：
key＝int(input(″请输入查找键：″))
i＝0
j＝8
f＝[0]*9
while i<＝j：
m＝(i＋j)∥2
f[m]＝1
if a[m]＝＝key：
break
if a[m]>key：
j＝m－1
else
i＝m＋1
C
A.1，1，0，0，1，0，0，0，0 B.0，0，0，0，1，0，0，0，0
C.0，0，0，0，1，1，1，1，0 D.0，1，1，1，1，0，0，0，0
解析　本题主要考查的是二分查找的过程。数组f中元素为1，表示查找过数组a对应位置上元素，f中元素为0，表示数组a对应位置上元素没有查找过；选项C查找的路径不符合二分查找算法的过程，答案为C。
6.有如下对分查找程序，A为按非降序排序的整型数组。
import random
key＝random.randint(0，4)*2＋20
a＝[12，14，15，15，19，x，20，24，y，26]
c＝0；n＝10；ans＝0
i＝0；j＝n－1
while i<＝j：
m＝(i＋j)∥2
if a[m]<＝key ：
i＝m＋1
else：
j＝m－1
c＋＝1
D
测试所有可能的key值，程序执行后c均等于4，下列正确的x，y值可以为(　　)
A.19，25 B.20，26 C.20，25 D.20，24
解析　由C始终等于4得，查找次数必定为4次，该对分查找并没有找到即break结束循环的语句，所以可以把该对分查找程序看作不断排除的过程，即i＞j表示排除完所有的数据节点，则程序结束，即对应的二叉排序树根据条件遍历到叶子节点为止。根据随机函数产生的key最小为20，若x为19，key＝20，则C等于3，排除A；若y是26，key＝24，则C为3，排除B；若y是25，key＝24，则C为3，排除C。
7.有如下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
D
A.1 B.2 C.3 D.4
解析　本题考查二分查找。列表长度就是二分查找的查找次数。列表共 8 个元素，最少 1 次，最多 4 次。查找到 76 时，不可能继续往右查找，所以 4 次是不可能的。
8.有如下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)
C
输入36，执行程序后，输出结果是(　　)
A.1 B.2 C.3 D.4
解析　本题考查二分查找。程序的功能是数组a的i索引前找一个数，满足a[i]*a[m]＝＝n的个数，因此分别是9*4、12*3、18*2。
9.某对分查找算法的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
D
A.a[1] B.a[4] C.a[12] D.a[16]
解析　本题考查二分算法以及二分判定树。根据本题代码m＝(i＋j＋1)∥2，画出二分判定树，位于二分判定树第4层的节点下标分别是1、4、7、9、12、14、17、19。所以key的值不可能是a[16]。
10.有如下Python程序段：
import random
d＝[28，37，39，42，45，50，70，80]
i，j，n＝0，len(d)－1，0
key＝random.randint(20，35)*2
while i<＝j：
　m＝(i＋j)∥2; n＋＝1
　 if key＝＝d[m]：
　break
　elif key　j＝m－1
　else：
　i＝m＋1
print(i，j，m，n)
B
执行该程序段后，下列说法正确的是(　　)
解析　考查二分查收算法思想。Key是[40，70]区间的偶数，n是循环次数。画出相应的二叉树。最多查找3次；a[1]为37，查找的位置不可能是1。若查找2次，说明查找的数是50，中间退出循环，满足条件i<＝j。
A.n的值可能为4
B.若n值为2，则必定满足i<＝j
C.m的值可能为1
D.若n值为3，则key的值可能是45
11.有如 Python 程序段：
import random
def find(x，y)：
　m＝(x＋y＋1)∥2
　　if a[m]＝＝key：
　return m
　if a[m]>key：
　y＝m－1
　else：
　x＝m＋1　
return find (x，y)
a＝[2，4，6，8，10，12，14，16]
key＝random.choice(a) #从序列的元素中随机挑选一个元素
i＝0；j＝len(a)－1
xb＝find(i，j)
print(xb，key)
解析　本题考查二分查找、自定义函数的综合应用。由“key＝random.choice(a)”可知查找键 key 是一定可以找得到的，由题中算法可知，找到最少找 1 次，最多找 int(log2n)＋1 次，本题中序列 a 中共有 8 个成员，则最多找 4 次。
上述程序执行完后，函数find被调用的最多次数是(　　)
A.3 B.4 C.5 D.6
B
12.有如下 Python 程序段：
import random
a＝[90，15，40，72，59，32，81，6]
b＝[7，1，5，2，4，3，6，0]
i，j＝0，len(a)－1
key＝random.randint(30，60)
p＝－1
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)
B
解析　本题考查索引排序和二分查找算法。key 值在 30－60，在列表 a 中只有 40、 59、32 符合范围，对应的索引值为2，4，5。
13.某二分查找算法的程序段如下：
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
C
执行该程序段后，下列说法正确的是(　　)
A.该程序若要实现对分查找，要求数组a按降序排列
B.若n为－2，则查找key值可能等于a[3]的值
C.若n为2，则查找 key 的值可能小于a[10]
D.n的值最小为－4，最大为4
解析　本题考查二分查找算法。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个。
14.已知一无序数组a，通过引入数组b，使得a[b[0]]≤a[b[1]]≤a[b[2]]……≤a[b[n－1]](示例如下图所示)，对这些有序数据可进行对分查找。则第一次查找时，中点位置m与中点值分别是(　　)
A.m的值是(n－1)∥2，中点值是a[m]
B.m的值是(n－1)∥2，中点值是a[b[m]]
C.m的值是(b[0]＋b[n－1])∥2，中点值是a[m]
D.m的值是(b[0]＋b[n－1])∥2，中点值是a[b[m]]
B
解析　本题主要考查的是对分查找算法。常见的错误思想为：根据a[b[0]]≤a[b[1]]…≤a[b[n－1]]可知数据是有序，因而想当然地认为：m的值为((b[0]＋b[n－1]∥2)，中点值是a[m]。其实，中间数据为a[b[(0＋n－1)∥2]]，例如 a[b[0]]≤a[b[1]]≤a[b[2]]，中点值为a[b[(0＋2)∥2))即a[b[1]]。因此，答案为B。
15.生成并输出二分查找树。在有序序列中查找某个数据，常使用二分查找算法。当待寻找的数据为随机值时，需要使用二分查找树列举所有可能情况。所谓二分查找树，是指按照二分查找的顺序，按层次输出以各中点元素为节点的二叉树。例如，当递增数组a＝[1，2，3，4，5，6，7，8，9，10，11，12，13，14，15，16]时，其对应的二分查找树如图所示。
下列代码能够生成并输出二分查找树，请回答下列问题：
(1)当有序数组a＝[2，23，40，45，60，65，68，83，86，95]时，对应的二分查找树中第3行第3个数为________。
(2)请在划线处填入合适的代码。
def create_bs(a)：　#生成并输出二分查找树
　　max_cnt＝0
　　n＝len(a)
　　pos＝[0]*n　#pos[i]表示元素a[i]查找的次数
　　for p in range(n)：
　 　　　L，R＝0，n－1
　　 　　cnt＝0
　　　 　while L<＝R：
　　　　 m＝___________
　　　　cnt＋＝1
　　　　if cnt>max_cnt：
　　　　 max_cnt＝cnt
　　　　if m＝＝p：
　　　　　pos[m]＝___________
　　　　　break
　　elif m　　　L＝m＋1
　　else：
　　　　R＝___________
for i in range(1，max_cnt＋1)：
　　s＝″″
　　for j in range(n)：
　　　if pos[j]＝＝i：　#找到节点a[j]
　　　　　　s＝s＋str(a[j])
　　　　else：
　　　　　　　　s＝s＋″　″
　　　　　print(s)
a＝list(range(1，17))
print(″有序数组：″，a)
print(″二分查找树：″)
create_bs(a)
答案　(1)65　(2)①(L＋R)∥2　②cnt　③m－1
解析　(1)按照题意画出二分查找树，可知第3行第3个数为65；(2)中点m表示式左偏，即m＝(L＋R)∥2；程序遍历数组a，计算当a[p]作为中点元素时，需要查找的次数，存储到数组pos中，即pos[p]表示元素a[p]查找的次数，则pos[m]＝cnt；按照二分查找算法思想，第③空为m－1。
16.小明学了排序和查找算法后，编写了一个处理成绩的程序，功能如下：程序运行时，首先从Excel文件中读取n个学生的技术成绩存储在列表b中，并对列表中的数据按升序进行排序；输入成绩 key，统计并输出共有多少位同学的成绩大于该成绩。
实现上述功能的Python程序如下，请在程序划线处填入合适的代码。
#从Excel文件中读取n个学生的技术成绩存储在列表b中，代码略
n＝len(b)
#对列表b中的元素进行升序排序
for i in range(1，n)：
tmp＝b[i]
j＝0
while ___________________：
j＝j＋1
if j！＝i：
for k in range(i，j，－1)：
　　　　b[k]＝b[k－1]
___________________
print(b)
key＝int(input(″please input key：″))
i，j＝0，n－1
while i<＝j：
m＝(i＋j)∥2
if keyj＝m－1
else：
i＝m＋1
print(″共有″＋___________________＋″位同学大于等于该成绩。″)
答案　①jb[j]或jb[j]
②b[k－1]＝tmp或b[j]＝tmp　③str(n－i)
解析　本题主要考查的是排序算法和二分查找算法。本题采用插入排序的方法对列表中的元素进行升序排序，划线①处while循环的功能是查找当前元素b[i]在前i－1个数中的插入位置，因为是升序排序，因此①处代码为jb[j]；
②处代码的功能是将当前元素(bmp)存储在插入位置(k－1)，因此②处代码为b[k－1]＝tmp；然后使用二分查找算法在列表b中查找大于key的第一个元素的位置，因为数据是升序排序，因此大于key的元素个数为n－i，由于print命令中使用“＋”运算符，因此需将“n－i”转换为字符类型，即划线③处代码为str(n－i)。课时5　二分查找
课时目标
1.通过实例分析，理解顺序查找的基本思想，掌握使用二分查找的一般方法。
2.能根据不同的应用场景，选择合适的数据结构，能灵活使用二分查找算法编写程序。
1.二分查找(Binary Search)
二分查找又称对分查找或折半查找。
二分查找是指在有序的数据序列中，首先将要查找的数据元素与数组的________________元素进行比较，如果相等，则查找成功并退出查找；否则，根据数组元素的有序性，确定新的____________(在数组的前半部分还是在后半部分)；在确定了新的查找范围后，重复进行以上操作，直到找到或查找结束为止。
①二分查找的前提条件是待查找的数据序列必须有序。
②“未找到”是指当前查找区间不存在，即区间左端点大于右端点。
2.二分查找的算法框架
说明：要查找的目标数据元素为key，待查找的数据元素存放在数组d中。
i、j分别为查找区间的起点位置和终点位置，m为查找区间的中间位置，n为数据元素个数。
i＝0
j＝n－1
while i<＝j：
#计算中点位置m
#比较key与d[m]，并做相应处理
#若i>j，则表示未找到
3.二分查找的程序实现
·设要查找的数据是key，待查找的数据元素存放在数组d中，并已按升序排序。
·输出查找结果，若找到则输出信息“找到！位置为：X”，否则输出“查无此数！”
·输出查找次数c。
二分查找主要代码如下(以升序为例)：
输入key的值
c＝0　　　　　　　#记录查找次数
find＝False　　　　#设置find的初值
i＝0　　　　　　　#区间左端点位置
j＝n－1　　　　　 #区间右端点位置
while ________________：　#还未找完并且还未找到，则继续查找
c＝c＋1　　　　#查找次数记数
m＝_________　 #计算中点位置m，等价于m＝int((i＋j)/2)
if key＝＝d[m]：　 #找到目标元素，并进行相应处理
find＝True
print(m)
if key>d[m]：　　#表示要查找的元素比中间位置上的元素大时
i＝m＋1　　　#调整区间左端点
else：　　　　　
j＝m－1　　　#调整区间右端点
if find＝＝False：
print(″查无此数！″)
print(″查找次数为：″，c)
例1 有如下两组数据：
①1，2，3，4，5，6，7，8，9
②3，4，5，2，1，8，7，6，9
要在上面两组数据中查找某个特定值，下列说法不正确的是(　　)
A.①②都可以直接使用二分查找
B.①②都可以直接使用顺序查找
C.①可以直接使用顺序查找，也可以直接使用二分查找
D.②可以直接使用顺序查找，但不能直接使用二分查找
听课笔记：　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
变式训练　分别使用顺序查找算法和二分查找算法在数据序列“5，6，10，13，15，20，21，26，30”中查找数据10，下列关于查找的次数的说法中正确的是(　　)
A.顺序查找2次，二分查找3次
B.顺序查找3次，二分查找2次
C.顺序查找3次，二分查找3次
D.顺序查找3次，二分查找4次
例2 在列表lista中存储的数据依次为：88，78，70，65，60，55，51，45，39，28。现使用二分查找算法在列表lista中查找数据51，共需查找的次数为(　　)
A.1次 B.2次 C.3次 D.4次
听课笔记：　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
变式训练　有100个英语单词已按升序排序并存储在列表listb中，现要使用二分查找算法在列表listb中查找某个单词，则最多的查找次数为(　　)
A.5次 B.6次 C.7次 D.8次
例3 某二分查找算法的Python程序段如下：
n＝0; flag＝True
key＝int(input(″输入要查找的数：″))
i，j＝0，9
while i<＝j and flag：
m＝(i＋j)∥2
if a[m]＝＝key：
flag＝False
elif a[m]i＝m＋1
n＝n＋1
else：
j＝m－1
n－＝1
若列表a中的元素依次是[5，11，18，23，27，33，34，41，45，69]，程序运行后变量n的值是2，则输入的整数key值不可能是(　　)
A.25 B.34 C.45 D.60
听课笔记：　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
变式训练　某二分查找算法的Python程序段如下：
b＝[98，86，81，77，66，60，48，20]
key＝int(input(″key＝″))
i，j＝0，len(b)－1
s＝″″
while i<＝j：
m＝(i＋j)∥2
if b[m]＝＝key：
s＝s＋″M″
break
if keyi＝m＋1
s＝s＋″R″
else：
j＝m－1
s＝s＋″L″
print(s)
程序执行时，输入key的值为55，则输出的结果为(　　)
A.RRL B.RLR C.RRLR D.RRLM
例4 有如下 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
听课笔记：　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
变式训练　有如下 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
1.列表a中存储了10个数据，依次为2、8、10、16、18、21、25、32、35、43，下列选项中不正确的是(　　)
A.使用顺序查找算法查找数据10，共查找了3次
B.使用二分查找算法查找数据10，共查找了3次
C.使用顺序查找算法查找数据25，共查找了7次
D.使用二分查找算法查找数据25，共查找了3次
2.在7个有序的数列“a1，a2，a3，a4，a5，a6，a7”中，采用二分查找法查找数值key，依次需要进行比较的数据可能是(　　)
A.a4 B.a4，a6，a2
C.a4，a2，a5 D.a4，a6，a5，a7
3.某对分查找算法的Python程序段如下：
a＝[85，74，70，65，54，36，30，28，26，12]
t＝″″
i，j＝0，9
key＝30
f＝False
while i<＝j and not f：
m＝(i＋j)∥2
t＋＝str(m)
if a[m]＝＝key：
f＝True
elif a[m]>key：
i＝m＋1
t＝t＋″→″
else：
j＝m－1
t＝t＋″←″
执行该程序段，变量t的值是(　　)
A.″4→7←5→″ B.″4→7←5→6→″
C.″4→7←5→6″ D.″4→7→5→6→″
4.某二分查找算法的Python程序段如下：
a＝[125，117，115，108，102，95，88，63，51，36]
key＝108
i，j＝0，len(a)－1
ss＝″″
while i<＝j：
m＝int((i＋j)/2＋0.5)
ss＝ss＋str(m)
if key＝＝a[m]：
break
if keyi＝m＋1
ss＝ss＋″>>″
else：
j＝m－1
ss＝ss＋″<<″
print(ss)
执行该程序段，输出的内容为(　　)
A.4<<1>>2>>3 　 B.5<<2<<4>>3
C.5<<2>>4<<3 D.5<<2>>4>>3
5.某对分查找算法的Python程序段如下：
n＝len(a)
f＝[0]*n
key＝int(input(″输入要查找的数：″))
i，j＝0，n－1
while i<＝j：
m＝(i＋j)∥2
f[m]＝1
if a[m]>＝key：
j＝m－1
else：
i＝m＋1
整型数组a为升序序列，输入待查找数，执行该程序段后，数组f中值为1的元素有3个，则n的值不可能(　　)
A.5 B.8 C.14 D.15
6.有如下Python程序段：
key＝int(input())
i＝0；j＝len(a)－1
s＝″″
while i<＝j：
　　m＝(i＋j＋1)∥2
　　if key＝＝a[m]：
break
　　if keyj＝m－1
　　else：
i＝m＋1
　　s＋＝str(a[m])＋″，″
print(s[：－1])
若数组元素a的值为[6，15，18，20，25，30，35，38，41，46]，输入正整数key值，执行该程序段，输出的值可能是(　　)
A.30，20 B.30，41，38
C.25，15，6 D.25，38，41
7.有如下 Python 程序：
import random
a＝[15，18，25，34，38，40，55，61，80，85]
key＝random.randint(15，55)
f＝[0]*10
i＝0；j＝len(a)－1
while i<＝j：
　　m＝(i＋j＋1)∥2
　　if a[m]>key：
　j＝m－1
　else：
　if a[m]%5＝＝0：
　　　f[m]＝1
　i＝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]
8.有如下 Python 程序段：
def binSearch(i，j，key)：
　if i>j：
　return－1
　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
课时5　二分查找
知识梳理
1.中间位置　查找范围
3.i<＝j and not find　(i＋j)∥2
例题精析
例1　A　[本题主要考查的是使用顺序查找和对分查找的适用条件。顺序查找对待查找的数据没有要求，而二分查找的前提是数据必须有序。①中数据有序，②中数据无序，①中数据顺序查找和二分查找均可以直接使用，②中数据只能使用顺序查找，若要使用二分查找，则先对②中数据进行排序操作。因此，不正确的是A，答案为A。]
变式训练　C　[本题主要考查的是顺序查找和二分查找的算法思想。数据10是数据序列中第3个元素，因此使用顺序查找时，共查找次数为3次，使用二分查找时，依次被访问的数据为15、6、10，即二分查找的次数也为3次。因此，答案为C。]
例2　D　[本题主要考查的是二分查找的查找过程。第一次找到的索引号为4的数据(60)，因为51<60，因此向右查找，第二次找到索引号为7的数据(45)，因为51>45，因此向左查找，第三次找到索引号为5的数据(55)，因为51<55，因此向右查找，第四次找到索引号为6的数据(51)，找到要找的数据后结束查找，因此共查找了4次，答案为D。]
变式训练　C　[本题主要考查的是计算二分查找的查找次数。N个数据，使用二分查找，查找次数最多为log2(n)取整加1，现共有100个单词，因此最多次数为7次，答案为C。]
例3　B　[本题主要考查二分查找算法。用二叉搜索树画出各个元素的搜索顺序，图中各个左子树方向可以让n自减，右子树方向可以让n自增。
A选项，若key＝25，则从节点23的右侧出循环，此时m、n的值是3、2，同理key＝45, m、n的值是8、2，key＝60，m、n的值是9、2。key＝34，m、n的值是6、1。]
变式训练　A　[本题主要考查的是二分查找时的方向问题。本题的功能是求使用二分查找在降序序列中查找数据55的过程，如果找到，则记为“M”，如果要查找的数据在序列的右边区间中，则记为“R”，否则记录为“L”。因此，答案为A。]
例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。]
变式训练　B　[本题考查二分查找的算法思想。根据题目要求，画出相应的二叉树，当找到#号时，向左查找，因此不可能找到B。]
随堂检测
1.D　[本题主要考查的是顺序查找和二分查找算法思想。使用二分查找算法查找数据25，需要的查找次数为4次，因此D选项不正确，答案为D。]
2.A　[本题考查二分查找的算法思想。第1次查找的是最中间的节点a4，因此A选项正确。B选项a2比a4小，查找到a6后，不可再去找a2。C选项a5比a4大，也不可能。D选项第3次查找，要么a5或a7，不可能2个数同时被查找到。]
3.C　[本题主要考查的是二分查找的程序实现。本题的功能是在一个降序数列中查找key的过程，记录每次访问的元素，并标识查找的方向(向右→或向左←)。在数列中查找30的过程中，第一次查找时，m＝4，t＝“4”，因为a[4]＝54>key，因此向右查找，i＝5，t＝“4→”；第二次查找时，m＝7，t＝“4→7”， 因为a[7]＝28key，因此向右查找，i＝6，t＝“4→7←5→”；第四次查找时，m＝6，t＝“4→7←5→6”， 因为a[6]＝＝key，因此查找结束，故答案为C。]
4.C　[本题主要考查的是二分查找的变式。本题中将中间位置m的计算公式修改为m＝int((i＋j)/2＋0.5)，即在偶数个数的区间中，找到的m为中间靠右的位置，因此，在查找数据108的过程中，依次访问的元素位置为5、2、4、3，注意左右方向的表示。查找结束时，字符串ss的内容为5<<2>>4<<3，答案为C。]
5.D　[本题考查对分查找的次数。本题为对分查找，数组f标记查找过的下标，若为3，表明共查找了3次。而该题中，查找找到不退出，退出的唯一条件是j。我们可以根据选项n的数量画出二叉判定树，若不存在从第三层结束的可能，就是不可能选项。]
6.B　[根据二分查找算法画出对应的二叉树为，可以得到遍历的路径。]
7.D　[考查二分查找算法的算法思想。f[m]赋值语句的执行条件 a[m]<＝key and a[m]%5＝＝0，即向右查找过程中，节点是5的倍数。产生数的范围是[15，55]，那么只可能查找[40，55]之间的数，第1次向右查找的节点为40，第2次查找的节点是55，即只能查找55。]
8.B　[本题考查递归法求二分查找，找到后返回中间位置，没有找到，累加找过的位置m。用索引位置画出二叉树为，没有一条分支节点和为8。]

展开更多......

收起↑