资源简介

专题12　查找算法
学习目标　
1.掌握对分查找核心算法思想，在一个[i，j]区间中，不断查找中间位置m，并不断更新查找区间(更新并画出左右端点)，直到找到或区间不存在；
2.掌握利用退出语句、标志变量和循环条件不成立的结束循环两种方式；
3.掌握查找区间不存在时，根据查找键值来判断变量i、j、m的关系.
在一个区间为[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肯定成立，则该数在序列中不存在。
(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
重难点1　二分查找的算法思想
若题目是要查找的数key已知，采用列表法比较快，用表格列出每次查找数组d的区间开始位置i、j和比较数的位置m及值a[m]，模拟对分查找的过程。中间位置m的计算公式为m＝(i＋j)∥2和m＝(i＋j＋1)∥2，当i＋j为奇数时，两者没有区别；当i＋j为偶数时，中间位置有两个，前者是中间偏左，后者是中间偏右。
例1 在存储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]
变式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程序段，若输入“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　#终止while循环
　 if a[m]＝＝key：
　　　 break
　 elif a[m]　　　 i＝m＋1
　 else：
　　　 j＝m－1
A.1 B.2 C.3 D.7
变式2 有如下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
重难点2　极值查找
当一个非降序序列中存在多个连续相等的数据key时，若要查找最左边key，设置的查找条件为当a[m]＝＝key时，还需移动j为m－1继续向左查找，当i>j即i＝j＋1时，查找的区间不存在，此时j指向的就是第1个小于等于key的值；若要查找最右边的key，当查找成功时，还需移动i为m＋1继续向右查找，此时i指向的就是第1个大于等于key的值。
例题 某二分查找算法的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
变式 有如下Python程序段：
import random
def binary(L，R，key)：
　　m＝(L＋R)∥2
　　if L>R：
　 return R
　　if key<＝a[m]：
　 return binary(m＋1，R，key)
　　else：
　 return binary(L，m－1，key)
a＝[9，8，7，7，7，5，5，3]
x＝random.randint(1，4)*2＋1
print(binary(0，7，x))
执行该程序段后，输出结果不可能是(　　)
A.1 B.4 C.6 D.7
重难点1　二分查找的算法思想
1.在7个有序的数列“a1，a2，a3，a4，a5，a6，a7”中，采用二分查找法查找数值key，依次需要进行比较的数据可能是(　　)
A.a4 B.a4，a6，a2
C.a4，a2，a5 D.a4，a6，a5，a7
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.有如下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] < target:
　 left ＝ mid ＋ 1
　　elif nums[mid] > target:
　 right ＝ mid － 1
该程序段运行后，列表lst的长度不可能为(　　)
A.1 B.2 C.3 D.4
4.有如下Python程序段：
import random
def find(x，y，key)：
　 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，key)
a ＝ [2，4，6，8，10，12，14，16]
key＝random.choice(a)　#从序列的元素中随机挑选一个元素
print(find(0，len(a)－ 1，key))
上述程序执行完后，函数 find 被调用的最多次数是(　　)
A.3 B.4 C.5 D.6
5.某二分查找算法的程序段如下：
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
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 种
重难点2　极值查找
1.某二分查找算法的 Python 程序段如下：
import random
key＝random.randint(1，4)*2
a＝[2，3，4，4，4，6，7，10]
ans＝0；i＝0；j＝len(a)－1
while i<＝j：
　 m＝(i＋j)∥2
　 if key>＝a[m]：
　 i＝m＋1
　 else：
　 j＝m－1
　 ans＋＝a[m]
print(ans)
执行该程序段后，ans 的值不可能是(　　)
A.27 B.14 C.11 D.9
2.有如下Python程序段：
a ＝ [15, 20, 32, 32, 54, 66, 94, 96]
f ＝ [0] * len(a)
key ＝ 2 * random.randint(10, 47) ＋ 1
i ＝ 0; j ＝ len(a) － 1; s ＝ 0; n ＝ 0
while i <＝ j：
　　m ＝ (i ＋ j ＋ 1) ∥ 2
　　f[m] ＝ 1
　　if key <＝ a[m]：
　 j ＝ m － 1; n ＝ n － 1
　　else：
　 i ＝ m ＋ 1; n ＝ n ＋ 1
s ＝ sum(f)
执行该程序段后，下列说法正确的是(　　)
A.变量i的值可能为3
B.变量n的值可能为3
C.变量s的值一定为3
D.变量f的值可能为[1，0，1，0，1，0，0，0]
3.有如下Python程序段：
#随机产生10个整型元素的非降序序列，依次存入列表a(a[0]！＝a[9])，代码略
a＝[]
key＝int(input())
i＝0；j＝9
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
4.如下Python程序实现的功能是：在非递增数组a中查找最后一个大于等于key的元素下标。
#读取一批非递增的数据保存在数组a中，代码略
key＝int(input(″请输入待查找的数据：″))
L，R＝0，len(a)－1
while L<＝R：
　 m＝(L＋R)∥2
　 if ①________：
　 L＝m＋1
　 else：
　 ②________
if R＝＝－1：
　　print(″不存在大于等于%d的数″%key)
else：
　　print(f″最后一个大于等于%s的元素下标是%d″%(key，③________ ))
划线处的内容是(　　)
A.①a[m]>key　　②R ＝ m　　 ③m
B.①a[m]>key　　②R ＝ m－1　③m
C.①a[m]>＝key　②R ＝ m－1　③R
D.①a[m]>＝key　②R ＝ m　　 ③R
重难点1　二分查找的算法思想
1.某二分查找算法的 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″
该程序段执行后，显示的内容可能是(　　)
A.RRRML B.LM
C.LMRL D.LRRM
2.某二分查找算法的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]
3.有如下 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
4.有如下 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)
程序运行后，变量p的值不可能是(　　)
A.2 B.3 C.4 D.5
5.如下 Python 程序段：
#导入模块并随机产生8个整型元素的非降序的奇数序列，并依次存入列表a[0]至a[7]，代码略
key＝random.randint(1，20)
i＝0；j＝7；s＝0
while i<＝j：
　　m＝(i＋j＋1)∥2
　　if a[m]＝＝key：
　 break
　　if a[m]>key：
　 j＝m－1
　 else：
　 i＝m＋1
　s＋＝ 1
执行上述程序段后，下列说法不正确的是(　　)
A.a[j]可能小于a[i]＋2
B.a[i]可能等于key
C.i一定等于j＋1
D.s的值一定小于等于4
6.有如下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)
执行该程序段后，下列说法正确的是(　　)
A.n的值可能为4
B.若n值为2，则必定满足i<＝j
C.m的值可能为1
D.若n值为3，则key的值可能是45
7.某二分查找算法的程序如下：
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
8.班里共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
9.有如下Python程序段：
def find_base(x，y)：
　 left, right ＝ 2, 10
　 while left <＝ right：
　 mid ＝ (left ＋ right) ∥ 2
　 value ＝ calc(mid, y)　#calc函数将mid进制的整数y转化为十进制数
　 if value ＝＝ x：
　　　 return mid
　 elif value < x：
　　　 left ＝ mid ＋ 1
　 else：
　　　 right ＝ mid － 1
　　return －1
x ＝ int(input()) ; y ＝ int(input())
print(find_base(x，y))
执行该程序段后，依次输入83和123，程序输出为(　　)
A.2 B.6 C.8 D.－1
10.有如下 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
11.有如下Python程序段：
import random
a＝[1，3，3，8，8，10，10，14，16，17]
key＝random.randint(0，9)*2
ans＝－1; f＝0
L＝0；R＝9
while L<＝R：
　　m＝(L＋R＋1)∥2
　　if a[m]＝＝key ：
　 ans＝m
　 break
　　if a[m]>key：
　 R＝m－1
　 f－＝1
　　else：
　 L＝m＋1
　 f＋＝1
运行该程序段后，关于f和ans的结果，下列说法正确的是(　　)
A.f可能的最小值为－3
B.f的值可能为－1
C.ans的值可能为1
D.ans的值不可能为3
12.小明为英文字母A～Z定义了一套全新的二进制编码规则，代码如下
s＝[chr(i＋65)for i in range(26)]
dc＝{}
for k in s：
　 i，j＝0，len(s)－1
　 rt＝″0″
　 while i<＝j：
　 m＝(i＋j)∥2
　 if s[m]＝＝k：
　　　 dc[k]＝rt
　　　 break
　 elif s[m]　　　 i＝m＋1
　　　 rt＋＝″1″
　 else：
　　　 j＝m－1
　　　 rt＋＝″0″
inp＝input(″请输入英文字符串：″).upper()#将输入的英文字母转为大写
for c in inp：
　 print(dc[c], end＝″″)
当程序运行后，输入“OK”后，其输出的二进制编码为(　　)
A.01001 0011 B.01001 000
C.00001 0011 D.01001 00110
重难点2　极值查找
1.有如下Python程序段：
from random import randint
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
2.某二分查找算法的Python程序段如下：
#生成若干数据有序排列后存储在列表d，代码略
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
3.有如下 Python 程序段：
a＝[34，35，38，41，41，41，45，45，69，78]
key＝41；n＝0
i＝0；j＝9
while i<＝j：
　　m＝(i＋j)∥2
　　if key　 j＝m－1
　　else：
　 i＝m＋1
该程序段运行结束后，下列说法正确的是(　　)
A.i的值是3 B.j的值是3
C.i的值是6 D.j的值是6
4.有如下 Python 程序段：
import random
a ＝ [1，3，4，6，6，6，9，9，11，12]
key ＝ random.randint(2，5) * 2
i，j ＝ 0，9
while i <＝ j：
　 m ＝ (i ＋ j) ∥ 2
　 if key < a[m]：
　 j ＝ m － 1
　 else：
　 i ＝ m ＋ 1
print(j)
执行该程序段后，输出的结果不可能是(　　)
A.2 B.3 C.5 D.7
5.某二分查找算法的Python程序如下：
#随机产生包含20个整型元素的升序序列，依次存入数组a，代码略
i＝0；j＝19；s＝″″
key＝int(input())
while i<＝j：
　　m＝(i＋j)∥2
　　s＋＝str(m)＋″，″
　　if a[m]>key：
　 j＝m－1
　　else：
　 i＝m＋1
执行上述程序并输入待查找数据，程序执行后，s的值不可能为(　　)
A.″9，4，1，0，″ B.″9，4，1，2，3，″
C.″9，4，6，5，″ D.″9，14，11，10，12，″
6.有如下Python程序：
a＝[0，20，23，23，24，24，31，48，49，73，75]
key＝int(input())
c＝0
i，j＝1，10
while i<＝j:
　 m＝(i＋j)∥2
　 if a[m]<＝key:
i＝m＋1
　 else:
j＝m－1
　 c＋＝1
print(c)
若程序运行后，输出的结果是 3，则输入的key可能是(　　)
A.20或73 B.24或49
C.23或24 D.23或49
专题12　查找算法
学习目标　
1.掌握对分查找核心算法思想，在一个[i，j]区间中，不断查找中间位置m，并不断更新查找区间(更新并画出左右端点)，直到找到或区间不存在；
2.掌握利用退出语句、标志变量和循环条件不成立的结束循环两种方式；
3.掌握查找区间不存在时，根据查找键值来判断变量i、j、m的关系.
在一个区间为[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肯定成立，则该数在序列中不存在。
(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，结束查找。
重难点1　二分查找的算法思想
若题目是要查找的数key已知，采用列表法比较快，用表格列出每次查找数组d的区间开始位置i、j和比较数的位置m及值a[m]，模拟对分查找的过程。中间位置m的计算公式为m＝(i＋j)∥2和m＝(i＋j＋1)∥2，当i＋j为奇数时，两者没有区别；当i＋j为偶数时，中间位置有两个，前者是中间偏左，后者是中间偏右。
例1 在存储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]
思维点拨
明考向 本题考查二分查找算法的程序实现。根据题意，画出查找的二叉树如图所示，当找到某个数字时，数组f中该数字对应索引位置上值赋值为1
精　点　拨 A 分别访问索引3，1，0
B 分别访问索引3，2，1，0，但该路径不存在
C 分别访问索引3，2，该路径也不存在
D 分别访问索引3，4，6，该路径也不存在
答案　A
变式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程序段，若输入“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　#终止while循环
　 if a[m]＝＝key：
　　　 break
　 elif a[m]　　　 i＝m＋1
　 else：
　　　 j＝m－1
A.1 B.2 C.3 D.7
思维点拨
明考向 本题考查二分查找的算法实现
精点拨 由7个字母构成一个搜索二叉树，如图所示，遍历树中每个节点，若搜索路径包含字母ch，则cnt的值增加1，查找BAC时包含字母B的节点个数
答案　C
变式2 有如下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。
重难点2　极值查找
当一个非降序序列中存在多个连续相等的数据key时，若要查找最左边key，设置的查找条件为当a[m]＝＝key时，还需移动j为m－1继续向左查找，当i>j即i＝j＋1时，查找的区间不存在，此时j指向的就是第1个小于等于key的值；若要查找最右边的key，当查找成功时，还需移动i为m＋1继续向右查找，此时i指向的就是第1个大于等于key的值。
例题 某二分查找算法的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
思维点拨
明考向 根据题意画出二叉树如图所示，当找到key时没有结束查找，而是继续向右查找
精　点　拨 A 若查找4，则为LRL，若查找5，则为LRRL
B 查找小于1的数，查找1，则为LLR，产生key的值不可能是1
C 查找8或9的结果是RRL，不可能是RLR
D 当查找大于等于12的数时，结果为RRRR
答案　D
变式 有如下Python程序段：
import random
def binary(L，R，key)：
　　m＝(L＋R)∥2
　　if L>R：
　 return R
　　if key<＝a[m]：
　 return binary(m＋1，R，key)
　　else：
　 return binary(L，m－1，key)
a＝[9，8，7，7，7，5，5，3]
x＝random.randint(1，4)*2＋1
print(binary(0，7，x))
执行该程序段后，输出结果不可能是(　　)
A.1 B.4 C.6 D.7
答案　A
解析　程序实现查找右极值的索引位置。产生x的范围是1，3，5，7，9，当找到后还要向右继续查找，因此属于查找右极值。
重难点1　二分查找的算法思想
1.在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个数同时被查找到。
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.有如下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] < target:
　 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次是不可能的。
4.有如下Python程序段：
import random
def find(x，y，key)：
　 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，key)
a ＝ [2，4，6，8，10，12，14，16]
key＝random.choice(a)　#从序列的元素中随机挑选一个元素
print(find(0，len(a)－ 1，key))
上述程序执行完后，函数 find 被调用的最多次数是(　　)
A.3 B.4 C.5 D.6
答案　B
解析　本题考查二分查找、自定义函数的综合应用。由“key＝random.choice(a)”可知查找键key是一定可以找得到的，由题中算法可知，找到最少找1次，最多找int(log2n)＋1次，本题中序列a中共有8个成员，则最多找4次。
5.某二分查找算法的程序段如下：
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个。
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 种
答案　A
解析　本题考查二分查找。列表a中的元素为1－15中的奇数，查找的key为2－16中的偶数，所以查找的结果不存在a[m]＝＝key也就是找到的情况，break不会被执行。查找的过程如下：s的值可能为－2，－1，1，3，共4种。
重难点2　极值查找
1.某二分查找算法的 Python 程序段如下：
import random
key＝random.randint(1，4)*2
a＝[2，3，4，4，4，6，7，10]
ans＝0；i＝0；j＝len(a)－1
while i<＝j：
　 m＝(i＋j)∥2
　 if key>＝a[m]：
　 i＝m＋1
　 else：
　 j＝m－1
　 ans＋＝a[m]
print(ans)
执行该程序段后，ans 的值不可能是(　　)
A.27 B.14 C.11 D.9
答案　C
解析　查找key值可能是2，4，6，8。当找到key后没有结束循环，而是查找向右的key，当key＝2时，ans＝4＋3＋2＝9；当key＝4时，ans＝4＋6＋4＝14；当 key＝6 时，ans＝4＋6＋7＝17；当 key＝8时，ans＝4＋6＋7＋10＝27。
2.有如下Python程序段：
a ＝ [15, 20, 32, 32, 54, 66, 94, 96]
f ＝ [0] * len(a)
key ＝ 2 * random.randint(10, 47) ＋ 1
i ＝ 0; j ＝ len(a) － 1; s ＝ 0; n ＝ 0
while i <＝ j：
　　m ＝ (i ＋ j ＋ 1) ∥ 2
　　f[m] ＝ 1
　　if key <＝ a[m]：
　 j ＝ m － 1; n ＝ n － 1
　　else：
　 i ＝ m ＋ 1; n ＝ n ＋ 1
s ＝ sum(f)
执行该程序段后，下列说法正确的是(　　)
A.变量i的值可能为3
B.变量n的值可能为3
C.变量s的值一定为3
D.变量f的值可能为[1，0，1，0，1，0，0，0]
答案　C
解析　程序的功能是查找[21，95]范围内的奇数key，若找到后还要向左查找。
3.有如下Python程序段：
#随机产生10个整型元素的非降序序列，依次存入列表a(a[0]！＝a[9])，代码略
a＝[]
key＝int(input())
i＝0；j＝9
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次。
4.如下Python程序实现的功能是：在非递增数组a中查找最后一个大于等于key的元素下标。
#读取一批非递增的数据保存在数组a中，代码略
key＝int(input(″请输入待查找的数据：″))
L，R＝0，len(a)－1
while L<＝R：
　 m＝(L＋R)∥2
　 if ①________：
　 L＝m＋1
　 else：
　 ②________
if R＝＝－1：
　　print(″不存在大于等于%d的数″%key)
else：
　　print(f″最后一个大于等于%s的元素下标是%d″%(key，③________ ))
划线处的内容是(　　)
A.①a[m]>key　　②R ＝ m　　 ③m
B.①a[m]>key　　②R ＝ m－1　③m
C.①a[m]>＝key　②R ＝ m－1　③R
D.①a[m]>＝key　②R ＝ m　　 ③R
答案　C
解析　在非递增数组a中查找最后一个大于等于key的元素，即当a[m]和key相等时，也要往后查找，排除选项A和B。当a[m]小于key时，索引位置m上值已经查找过了，因此可以不查找。
重难点1　二分查找的算法思想
1.某二分查找算法的 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″
该程序段执行后，显示的内容可能是(　　)
A.RRRML B.LM
C.LMRL D.LRRM
答案　A
解析　根据算法画出二叉树如图所示，找到后并不结束循环。
2.某二分查找算法的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]。
3.有如下 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。
4.有如下 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)
程序运行后，变量p的值不可能是(　　)
A.2 B.3 C.4 D.5
答案　B
解析　本题考查索引排序和二分查找算法。key值在30－60(60取不到)，在列表a中只有40、59、32符合范围，对应的索引值为2，4，5。
5.如下 Python 程序段：
#导入模块并随机产生8个整型元素的非降序的奇数序列，并依次存入列表a[0]至a[7]，代码略
key＝random.randint(1，20)
i＝0；j＝7；s＝0
while i<＝j：
　　m＝(i＋j＋1)∥2
　　if a[m]＝＝key：
　 break
　　if a[m]>key：
　 j＝m－1
　 else：
　 i＝m＋1
　s＋＝ 1
执行上述程序段后，下列说法不正确的是(　　)
A.a[j]可能小于a[i]＋2
B.a[i]可能等于key
C.i一定等于j＋1
D.s的值一定小于等于4
答案　C
解析　A选项数组是一个非降序的奇数序列，当找不到的情况下，j小于i，a[j]可能小于 a[i]＋2。C选项若数据能找到，则i小于或等于j。D选项8个数据最多查找4次。
6.有如下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)
执行该程序段后，下列说法正确的是(　　)
A.n的值可能为4
B.若n值为2，则必定满足i<＝j
C.m的值可能为1
D.若n值为3，则key的值可能是45
答案　B
解析　考查二分查收算法思想。Key是[40，70]区间的偶数，n是循环次数。画出相应的二叉树。最多查找3次；a[1]为37，查找的位置不可能是1。若查找2次，说明查找的数是50，中间退出循环，满足条件i<＝j。
7.某二分查找算法的程序如下：
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次。
8.班里共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必定指向不符合条件的第一个位置，即所找同学学号。
9.有如下Python程序段：
def find_base(x，y)：
　 left, right ＝ 2, 10
　 while left <＝ right：
　 mid ＝ (left ＋ right) ∥ 2
　 value ＝ calc(mid, y)　#calc函数将mid进制的整数y转化为十进制数
　 if value ＝＝ x：
　　　 return mid
　 elif value < x：
　　　 left ＝ mid ＋ 1
　 else：
　　　 right ＝ mid － 1
　　return －1
x ＝ int(input()) ; y ＝ int(input())
print(find_base(x，y))
执行该程序段后，依次输入83和123，程序输出为(　　)
A.2 B.6 C.8 D.－1
答案　C
解析　本题考查进制转换与二分查找。函数find_base(x，y)的功能为通过二分查找算法查找十进制数x对应另一进制数y的基数，如果不存在则返回－1。由于123O＝83D，最后能够找到对应的基数为8。
10.有如下 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。
11.有如下Python程序段：
import random
a＝[1，3，3，8，8，10，10，14，16，17]
key＝random.randint(0，9)*2
ans＝－1; f＝0
L＝0；R＝9
while L<＝R：
　　m＝(L＋R＋1)∥2
　　if a[m]＝＝key ：
　 ans＝m
　 break
　　if a[m]>key：
　 R＝m－1
　 f－＝1
　　else：
　 L＝m＋1
　 f＋＝1
运行该程序段后，关于f和ans的结果，下列说法正确的是(　　)
A.f可能的最小值为－3
B.f的值可能为－1
C.ans的值可能为1
D.ans的值不可能为3
答案　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。
12.小明为英文字母A～Z定义了一套全新的二进制编码规则，代码如下
s＝[chr(i＋65)for i in range(26)]
dc＝{}
for k in s：
　 i，j＝0，len(s)－1
　 rt＝″0″
　 while i<＝j：
　 m＝(i＋j)∥2
　 if s[m]＝＝k：
　　　 dc[k]＝rt
　　　 break
　 elif s[m]　　　 i＝m＋1
　　　 rt＋＝″1″
　 else：
　　　 j＝m－1
　　　 rt＋＝″0″
inp＝input(″请输入英文字符串：″).upper()#将输入的英文字母转为大写
for c in inp：
　 print(dc[c], end＝″″)
当程序运行后，输入“OK”后，其输出的二进制编码为(　　)
A.01001 0011 B.01001 000
C.00001 0011 D.01001 00110
答案　A
解析　构建一棵26个节点的升序二叉树，由于26小于31，因此最多查找4次，用一个4位二进制数存储访问的节点(标记为1)。
重难点2　极值查找
1.有如下Python程序段：
from random import randint
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的值是相等的。
2.某二分查找算法的Python程序段如下：
#生成若干数据有序排列后存储在列表d，代码略
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]3.有如下 Python 程序段：
a＝[34，35，38，41，41，41，45，45，69，78]
key＝41；n＝0
i＝0；j＝9
while i<＝j：
　　m＝(i＋j)∥2
　　if key　 j＝m－1
　　else：
　 i＝m＋1
该程序段运行结束后，下列说法正确的是(　　)
A.i的值是3 B.j的值是3
C.i的值是6 D.j的值是6
答案　C
解析　本题考查二分查找。当找到key时，没有结束循环，而是向右继续查找。最后一个41的索引位置为5，因此找到后，i向后查找，i 的值是6。
4.有如下 Python 程序段：
import random
a ＝ [1，3，4，6，6，6，9，9，11，12]
key ＝ random.randint(2，5) * 2
i，j ＝ 0，9
while i <＝ j：
　 m ＝ (i ＋ j) ∥ 2
　 if key < a[m]：
　 j ＝ m － 1
　 else：
　 i ＝ m ＋ 1
print(j)
执行该程序段后，输出的结果不可能是(　　)
A.2 B.3 C.5 D.7
答案　B
解析　 本题考查二分查找的算法思想。产生一个[4，10]之间的偶数，当key＝＝a[m]时，没有终止查找，还是继续向右查找，直至i>j。若key值为4，j的值为2；若key值为6和8，j的值为5；若key值为10，j的值为7。
5.某二分查找算法的Python程序如下：
#随机产生包含20个整型元素的升序序列，依次存入数组a，代码略
i＝0；j＝19；s＝″″
key＝int(input())
while i<＝j：
　　m＝(i＋j)∥2
　　s＋＝str(m)＋″，″
　　if a[m]>key：
　 j＝m－1
　　else：
　 i＝m＋1
执行上述程序并输入待查找数据，程序执行后，s的值不可能为(　　)
A.″9，4，1，0，″ B.″9，4，1，2，3，″
C.″9，4，6，5，″ D.″9，14，11，10，12，″
答案　 D
解析　分析程序可知，s为二分过程中生成中值m的顺序，该顺序应是二分找找判定树中的一部分，四个选项的部分判定树如下所示。其中D选项中的节点12不应在节点11的左侧，因此D选项错误。
6.有如下Python程序：
a＝[0，20，23，23，24，24，31，48，49，73，75]
key＝int(input())
c＝0
i，j＝1，10
while i<＝j:
　 m＝(i＋j)∥2
　 if a[m]<＝key:
i＝m＋1
　 else:
j＝m－1
　 c＋＝1
print(c)
若程序运行后，输出的结果是 3，则输入的key可能是(　　)
A.20或73 B.24或49
C.23或24 D.23或49
答案　B
解析　本题考查二分查找。查找范围是[1，10]，当找到key时仍要往右边查找，当key＝20、24、49时，查找的次数是3，当key＝23、31、73时，查找的次数是4。(共80张PPT)
第二部分　算法与程序设计
专题12　查找算法
1.掌握对分查找核心算法思想，在一个[i，j]区间中，不断查找中间位置m，并不断更新查找区间(更新并画出左右端点)，直到找到或区间不存在；
2.掌握利用退出语句、标志变量和循环条件不成立的结束循环两种方式；
3.掌握查找区间不存在时，根据查找键值来判断变量i、j、m的关系.
目 录
CONTENTS
体系构建
01
真题再现
02
考点精练
03
当堂检测
04
课后练习
05
体系构建
1
在一个区间为[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肯定成立，则该数在序列中不存在。
真题再现
2
(2024年1月浙江省选考)某算法的部分流程图如图所示，若n的值为7，key的值为78，数组元素a[0]至a[n－1]依次存放7，12，24，36，55，78，83，执行这部分流程后，输出c的值为(　　)
解析　本题考查二分查找算法。变量c表示移动左边界向右查找的次数。查找78的过程为先找到36，向查查找1次，找到78，结束查找。
B
A.0 B.1
C.2 D.3
考点精练
3
重难点1　二分查找的算法思想5
若题目是要查找的数key已知，采用列表法比较快，用表格列出每次查找数组d的区间开始位置i、j和比较数的位置m及值a[m]，模拟对分查找的过程。中间位置m的计算公式为m＝(i＋j)∥2和m＝(i＋j＋1)∥2，当i＋j为奇数时，两者没有区别；当i＋j为偶数时，中间位置有两个，前者是中间偏左，后者是中间偏右。
运行该程序，输出的结果可能是(　　)
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，该路径也不存在
解析　本题考查二分查找的算法思想。根据题目要求，画出相应的二叉树，当找到#号时，向左查找，因此不可能找到B。
B
思维点拨
明考向 本题考查二分查找的算法实现
精点拨 由7个字母构成一个搜索二叉树，如图所示，遍历树中每个节点，若搜索路径包含字母ch，则cnt的值增加1，查找BAC时包含字母B的节点个数
答案　C
解析　本题考查二分查找。程序的功能是数组a的i索引前找一个数，满足a[i]*a[m]＝＝n的个数，因此分别是9*4、12*3、18*2。
C
重难点2　极值查找
当一个非降序序列中存在多个连续相等的数据key时，若要查找最左边key，设置的查找条件为当a[m]＝＝key时，还需移动j为m－1继续向左查找，当i>j即i＝j＋1时，查找的区间不存在，此时j指向的就是第1个小于等于key的值；若要查找最右边的key，当查找成功时，还需移动i为m＋1继续向右查找，此时i指向的就是第1个大于等于key的值。
D
思维点拨
明考向 根据题意画出二叉树如图所示，当找到key时没有结束查找，而是继续向右查找
精　点　拨 A 若查找4，则为LRL，若查找5，则为LRRL
B 查找小于1的数，查找1，则为LLR，产生key的值不可能是1
C 查找8或9的结果是RRL，不可能是RLR
D 当查找大于等于12的数时，结果为RRRR
A
解析　程序实现查找右极值的索引位置。产生x的范围是1，3，5，7，9，当找到后还要向右继续查找，因此属于查找右极值。
当堂检测
4
重难点1　二分查找的算法思想
重难点2　极值查找
1.在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个数同时被查找到。
解析　根据题意，图出对应的二叉树，可以得到相应的查找路径。
答案　B
解析　本题考查二分查找。列表长度就是二分查找的查找次数。列表共8个元素，最少1次，最多4次。查找到76时，不可能继续往右查找，所以4次是不可能的。
D
解析　本题考查二分查找、自定义函数的综合应用。由“key＝random.choice(a)”可知查找键key是一定可以找得到的，由题中算法可知，找到最少找1次，最多找int(log2n)＋1次，本题中序列a中共有8个成员，则最多找4次。
B
解析　本题考查二分查找算法。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个。
执行该程序段后，下列说法正确的是(　　)
A.该程序若要实现二分查找，要求数组a按降序排列
B.若n为－2，则查找key值可能等于a[3]的值
C.若n为2，则查找 key 的值可能小于a[10]
D.n的值最小为－4，最大为4
C
解析　本题考查二分查找。列表a中的元素为1－15中的奇数，查找的key为2－16中的偶数，所以查找的结果不存在a[m]＝＝key也就是找到的情况，break不会被执行。查找的过程如下：s的值可能为－2，－1，1，3，共4种。
A
解析　查找key值可能是2，4，6，8。当找到key后没有结束循环，而是查找向右的key，当key＝2时，ans＝4＋3＋2＝9；当key＝4时，ans＝4＋6＋4＝14；当 key＝6 时，ans＝4＋6＋7＝17；当 key＝8时，ans＝4＋6＋7＋10＝27。
执行该程序段后，ans 的值不可能是(　　)
A.27 B.14 C.11 D.9
C
执行该程序段后，下列说法正确的是(　　)
A.变量i的值可能为3
B.变量n的值可能为3
C.变量s的值一定为3
D.变量f的值可能为[1，0，1，0，1，0，0，0]
C
解析　程序的功能是查找[21，95]范围内的奇数key，若找到后还要向左查找。
执行上述程序段后，下列说法
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次。
C
解析　在非递增数组a中查找最后一个大于等于key的元素，即当a[m]和key相等时，也要往后查找，排除选项A和B。当a[m]小于key时，索引位置m上值已经查找过了，因此可以不查找。
课后练习
5
重难点1　二分查找的算法思想
重难点2　极值查找
该程序段执行后，显示的内容可能是(　　)
A.RRRML B.LM
C.LMRL D.LRRM
A
解析　根据算法画出二叉树如图所示，找到后并不结束循环。
数组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]。
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
解析　本题考查索引排序和二分查找算法。key值在30－60(60取不到)，在列表a中只有40、59、32符合范围，对应的索引值为2，4，5。
C
解析　A选项数组是一个非降序的奇数序列，当找不到的情况下，j小于i，a[j]可能小于 a[i]＋2。C选项若数据能找到，则i小于或等于j。D选项8个数据最多查找4次。
执行上述程序段后，下列说法
A.a[j]可能小于a[i]＋2
B.a[i]可能等于key
C.i一定等于j＋1
D.s的值一定小于等于4
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
C
解析　根据列表a的值，画出如图所示二叉树，当向右查找时，c的值增加1，查找29，向右查找2次，若查找30，在查找29的基础上，再向右查找一次，因此需查找3次。
若a＝[2，13，14，19，23，26，29，31，32，38]，运行该程序段后，c的值为2，则key的值不可能是(　　)
A.19 B.29 C.30 D.32
C
解析　共有n－2位学生交作业，当条件a[m]＝＝m成立，说明未交作业的学生在后半段，因此移到L，反之向左查找R＝m－1。考虑查找结束的极限情况，L必定指向不符合条件的第一个位置，即所找同学学号。
C
解析　本题考查进制转换与二分查找。函数find_base(x，y)的功能为通过二分查找算法查找十进制数x对应另一进制数y的基数，如果不存在则返回－1。由于123O＝83D，最后能够找到对应的基数为8。
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
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。
解析　构建一棵26个节点的升序二叉树，由于26小于31，因此最多查找4次，用一个4位二进制数存储访问的节点(标记为1)。
A
数组元素 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的值是相等的。
程序运行后，变量n的值为2，输出的内容可能是(　　)
A.4 7 7 B. 10 4 12
C.7 6 7 D.9 12 15 18
A
解析　本题考查二分查找算法。如果条件d[m]该程序段运行结束后，下列说法正确的是(　　)
A.i的值是3 B.j的值是3
C.i的值是6 D.j的值是6
C
解析　本题考查二分查找。当找到key时，没有结束循环，而是向右继续查找。最后一个41的索引位置为5，因此找到后，i向后查找，i 的值是6。
执行该程序段后，输出的结果不可能是(　　)
A.2 B.3 C.5 D.7
B
解析　 本题考查二分查找的算法思想。产生一个[4，10]之间的偶数，当key＝＝a[m]时，没有终止查找，还是继续向右查找，直至i>j。若key值为4，j的值为2；若key值为6和8，j的值为5；若key值为10，j的值为7。
执行上述程序并输入待查找数据，程序执行后，s的值不可能为(　　)
A.″9，4，1，0，″ B.″9，4，1，2，3，″
C.″9，4，6，5，″ D.″9，14，11，10，12，″
D
解析　分析程序可知，s为二分过程中生成中值m的顺序，该顺序应是二分找找判定树中的一部分，四个选项的部分判定树如下所示。其中D选项中的节点12不应在节点11的左侧，因此D选项错误。
若程序运行后，输出的结果是 3，则输入的key可能是(　　)
A.20或73 B.24或49
C.23或24 D.23或49
B
解析　本题考查二分查找。查找范围是[1，10]，当找到key时仍要往右边查找，当key＝20、24、49时，查找的次数是3，当key＝23、31、73时，查找的次数是4。

展开更多......

收起↑