资源简介

专题18　查找算法
学业要求 知　识　点 学业水平等级
1.掌握对分查找的核心算法思想并用程序代码实现 4
2.掌握利用二叉树来描述查找的路径或区间 4
知识点一　二分查找的算法思想
【知识梳理】
1.________又称检索，计算机根据所给条件查找出满足条件的对象，即在存储的一批数据内寻找出一个特定的数据，或者确定在该批数据内是否存在这样的数据。若没有找到满足条件的对象，则返回特定值，表明查找失败；若查找到满足条件的对象，则表明查找成功，一般要求返回该对象的存储位置或对象值本身。
2.________________又称线性查找，从顺序表的一端开始，依次将每个元素的关键字与给定值key(查找键)进行比较。若某个元素的关键字等于key，则表明查找成功；若所有元素都比较完毕仍找不到，则表明查找失败。
3.________________又称折半查找，对分查找。它是一种效率很高的查找算法，但被查找的数据序列必须是有序的。
4.二分查找首先将查找键与____________处于________的元素进行比较，如果中间位置上的元素的数值与查找键不同，根据数组元素的有序性，就可确定在数组的________还是________继续查找；在新确定的范围内，继续按上述方法进行查找，直到获得最终结果。
5.二分查找算法描述：在一个区间为[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肯定成立，则该数在序列中不存在。
【经典案例】
二分查找中间位置m的计算公式为m＝(i＋j)//2和m＝(i＋j＋1)//2，当i＋j为奇数时，两者没有区别；当i＋j为偶数时，中间位置有两个，前者是中间偏左，后者是中间偏右。利用判定二叉树快速解题，同时确定查找路径。当查找中间结点时，还可以继续查找，因此查找不成功一定发生在叶子结点。在查找一个数的路径确定每次查找的数位置和值，可以判断查找次数，若在找不到该数据时，可以判断此时变量i、j和m的值。大致可以分为以下几种情况：①随机给出查找值，求查找次数或查找路径；②给出查找次数或查找路径，求查找值的范围；③当查找成功时没有结束查找，求查找次数或查找的边界值。
【例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。
听课笔记：____________________________________________________________
______________________________________________________________________
______________________________________________________________________
【变式1】 有如下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
【例2】 有如下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]
思维点拨
明考向 本题考查二分查找算法的算法思想
精点拨 f[m]赋值语句的执行条件a[m]<＝key and a[m]%5＝＝0，即向右查找过程中，节点是5的倍数。产生数的范围是[15，55]，那么只可能查找[40，55]之间的数，第1次向右查找的节点为40，第2次查找的节点是55，即只能查找55
听课笔记：_____________________________________________________________
______________________________________________________________________
______________________________________________________________________
【变式2】 有如下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
知识点二　极值查找
【知识梳理】
1.查找结束可能是2种情况，一是当a[m]和key相等时，找到要查找的元素，采用________语句退出循环，二是查找的区间________存在，即左区间i大于右区间j。
2.在一个非降序序列中查找一个不存在的数key时，查找的区间不断地缩小，最后一次查找时，区间中只有________个元素，即左区间i等于右区间j。若a[m]大于key，则移动右区间j，左区间i保持不变，此时变量j＝i－1；若a[m]小于key，则移动左区间i，右区间保持j不变，此时变量i＝j＋1。因此二分查找算法结束后，若查找的数据不存在，肯定有i＝________的等量关系。
3.当一个非降序序列中存在多个与key相等的数据时，若要找到第1个小于key或者最左边的key，称为左极值，算法为：当a[m]________于key时，并没有采用break语句退出循环，而是继续向左查找，由于找到后，j向左移动，因此j不可能指向key，最左边key位置为i。
4.右极值指的是要找到第1个大于key或者最右边的key，算法为：当a[m]等于key时，继续向________查找，由于找到后，i向右移动，因此i不可能指向key，最右边key位置为j。
【经典案例】
当一个非降序序列中存在多个连续相等的数据key时，若要查找最左边key，设置的查找条件为当a[m]＝＝key时，还需移动j为m－1继续向左查找，当i>j即i＝j＋1时，查找的区间不存在，此时j指向的就是第1个小于等于key的值；若要查找最右边的key，当查找成功时，还需移动i为m＋1继续向右查找，此时i指向的就是第1个大于等于key的值。
【例题】 某对分查找算法的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 查找数据69，查找路径34，42，52，3次向右移动，第4次找到了
B 查找数据23，但是找到23后，还是要向左查找，直至区间不存在，即LMLR
C 查找数据23，但是找到23后，还是要向左查找，不是向右查找
D 向左找到23，向右找到29，再向右查找比29大比34小的数，不可能再次向右查找
听课笔记：_____________________________________________________________
______________________________________________________________________
______________________________________________________________________
【变式】 某Python程序段如下：
import random
a＝[0]*8；a[0]＝1
for i in range(1，8)：
a[i]＝a[i－1]＋random.randint(1，10)
n＝0；key＝5
i，j＝0，7
while i<＝j：
m＝(i＋j)//2；n＋＝1
if a[m]<＝key：
　　 　　i＝m＋1
else：
　　　　 j＝m－1
print(n)
执行该程序段后，输出的结果是(　　)
A.1 B.2
C.3 D.4
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程序段：
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 keyj＝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
3.有如下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
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
5.某对分查找的Python程序如下：
from random import randint
a＝[19，17，16，14，13，11，9，7]
key＝randint(0，4)*2＋9
i＝0；j＝7；c＝0
while　i<＝j：
c＝c＋1
m＝(i＋j)//2
if a[m]>key：
i＝m＋1
else：
j＝m－1
该程序段执行后，下列说法不正确的是(　　)
A.j的值可能为1 B.c的值一定等于3
C.i的值一定等于j＋1 D.i的值一定不等于7
6.某二分查找算法的Python程序如下：
import random
key＝random.randint(0，4)*2＋5
n＝10
ans＝0
a＝[4，5，5，8，9，11，11，13，15，17]
i＝0
j＝n－1
while i<＝j：
m＝(i＋j)//2
if a[m]<＝key：
i＝m＋1
else：
j＝m－1
ans＋＝a[m]
print(ans)
程序运行后，输出ans的值不可能是(　　)
A.19 B.27
C.37 D.44
7.如下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
8.某Python程序如下：
a＝[86，75，58，46，20，18，12，5]
key＝int(input())
n＝0；i＝0；j＝len(a)－1
while i<＝j：
m＝(i＋j)//2
if key>a[m]：
j＝m－1；n＝n－1
else：
i＝m＋1；n＝n＋1
当输入不同的 key 值，运行该程序段后，n的值可能有(　　)
A.5种 B.6种
C.7种 D.8种
专题18　查找算法
知识点一
知识梳理
1.查找(Search)
2.顺序查找(Sequential Search)
3.二分查找(Binary Search)
4.有序数组内　中间位置　前半部分　后半部分
经典案例
例1　B
变式1　D　[本题考查二分查找。画出二叉树，随机生成[20，70]区间内的一个正整数，最少查找1次，最多4次，但查找大于76的数时，才要查找4次。每查找一次，将查找的区间添加到lst中，所以长度4次是不可能的。]
例2　D
变式2　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。]
知识点二
知识梳理
1.break　不　2.一　j＋1　3.等　4.右
经典案例
例题　A
变式　C　[本题考查二分查找。根据题意画出判定二叉树如图所示。如果条件a[m]<＝key成立，还要向右继续查找，因此除了查找大于等于a[6]的数据，均要查找3次，a[0]的值1，随机产生一个比前一项至少大1的数，因此a[6]至少是7，只需找3次。]
当堂过关检测
1.A　[本题考查二分查找的算法思想。第1次查找的是最中间的节点a4，因此A选项正确。B选项a2比a4小，查找到a6后，不可再去找a2。C选项a5比a4大，也不可能。D选项第3次查找，要么a5或a7，不可能2个数同时被查找到。]
2.B　[本题考查二分查找算法思想。key是[40，70]区间的偶数，n是循环次数。画出相应的二叉树。最多查找3次；a[1]为37，查找的位置不可能是1。若查找2次，说明查找的数是50，中间退出循环，满足条件i<＝j。]
3.B　[本题考查索引排序和二分查找算法。key值在30－60，在列表a中只有40、59、32符合范围，对应的索引值为2、4、5。]
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。]
5.A　[本题考查二分查找算法思想。数组a为降序数列，key的取值范围是9～17之间的奇数，当找到key时不要向左继续查找，结束查找时，j小于i，且i等于j＋1，位置i是最接近要查找的。A选项查找17，j的值为0，查找15，j的值为2。D选项key最小值是9，因此i的值最大值是6。]
6.A　[本题考查二分查找算法。变量key的值可能是[5，7，9，11，13]，ans是查找值的累加和。当找到key时，还要向右边界继续查找。当key＝5、7时，a[m]分别是：9、5、5、8，ans＝27，由此可以推断不可能是19。]
7.C　[查找最后一个大于等于该数应该是查找右极值，即找到后还要向右查找。最终R指向是要查找的数。]
8.A　[本题考查二分查找。中点计算方式为左偏，查找二叉树如下：
变式在于相等不退出，而是继续向右找，key为任意数，无论是否找到，最终都从虚线处走出。向左加1，向右减1，分析二叉树可知，n值可能为：－3，－1，1，2，4这5种。]

展开更多......

收起↑