专题12 查找算法 学案（含解析）2025届高中信息技术.DOCX
专题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)
whilei＝j：
m＝(i＋j)∥2
f[m]＝1
ifkey＝＝a[m]：
break
ifkeya[m]：
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程序段：
importrandom
a＝[A,#,B,C,D,E,#,F]
i＝0
j＝len(a)－1
x＝random.choice(ABCDEF)#从字符串ABCDEF中随机选出一个字符
whilei＝j：
mid＝(i＋j)∥2
ifa[mid]＝＝x:
break
elifa[mid]＝＝#ora[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
forkeyina：
i，j＝0，len(a)－1
whilei＝j：
m＝(i＋j)∥2
ifa[m]＝＝ch：
cnt＋＝1；break#终止while循环
ifa[m]＝＝key：
break
elifa[m]key：
i＝m＋1
else：
j＝m－1
A.1B.2C.3D.7
变式2有如下Python代码：
n＝int(input(″请输入一个数：″))
a＝[iforiinrange(n)]
c＝0
foriinrange(1，n)：
L＝1；R＝i－1
whileL＝R：
m＝(L＋R)∥2
ifa[i]*a[m]＝＝n：
c＋＝1
break
elifa[i]*a[m]n：
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继续向左查找，当ij即i＝j＋1时，查找的区间不存在，此时j指向的就是第1个小于等于key的值；若要查找最右边的ke