专题12　查找算法 课件 2025届高中信息技术.pptx

第二部分算法与程序设计专题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，结束查找。BA.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，0B分别访问索引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继续向左查找，当ij即i＝j＋1时，查找的区间不存在，此时j指向的就是第1个小于等于key的值；若要查找最右边的key，当查找成功时，还需移动i为m＋1继续向右查找，此时i指向的就是第1个大于等于key的值。

D

思维点拨明考向根据题意画出二叉树如图所示，当找到key时没有结束查找，而是继续向右查找精点拨A若查找4，则为LRL，若查找5，则为LRRLB查找小于1的数，查找1，则为LLR，产生key的值不可能是1C查找8或9的结果是RRL，不可能是RLRD当查找大于等于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，a7A解析本题考查二分查找的算法思想。第1次查找的是最中间的节点a4，因此A选项正确。B选项a2比a4小，查找到a6后，不可再去找a2。C选项a5比a4大，也不可能。D选项第3次查找，要么a5或a7，不可能2个数同时被查找到。

解析根据题意，图出对应的二叉树，可以得到相应的查找路径。答案B

解析本题考查二分查找。列表长度就是二分查找的查找次数。列表共8个元素