从选考试题看对分查找算法问题的 解题策略

傅琳璐

对分查找算法作为程序设计中的经典算法之一，是一种高效的查找方法。纵观浙江省2015—2020年的信息技术选考试题，可发现对分查找算法是每年选考试题中的必考內容。从最开始简单的查找区间计算，到算法思想应用……再到今年的对分查找变形程序分析，试题考查内容的角度在变，难度也在逐步增大。这就要求学生在平时的学习过程中不仅要深入理解对分查找算法思想，建立良好的算法思维和计算思维，还要掌握一定的解题策略，具备良好的解题能力，只有这样才能在选考考试中做到“仓里有粮，心中不慌”。

● 勤用列表追踪查找过程

例1.（2017.4选考真题）某对分查找算法的VB程序段如图1所示。数组元素a（1）到a（10）的值依次为“8，17，24，30，36，40，55，58，61，66”，文本框Text1中输入的值是30，执行该程序段，文本框Text2中显示的是（  ）。

A.40 24   B.40 24 36

C.36 24   D.36 17 24

剖析：此题为对分查找过程分析题，查找键key值已知，所求文本框Text2中显示的内容为对分查找过程中找到key值之前依次访问到的数据a（m），解题时可用列表法记录对分查找过程中各个变量值的变化（如下表）。

点评：列表法是解决对分查找问题最简单有效的方法，过程清晰，一目了然。用列表法将对分查找算法执行一遍，可以清楚准确地观察到查找过程中各个变量值的变化，同时还可以帮助学生巩固算法过程，加深对算法思想的理解，答题正确率高，非常适合算法的初学者。但是列表法比较费时，在遇到对分查找次数较多或查找键key值未知，查找过程不唯一的问题时，解题效率不高。

● 活用特征判断程序结果

例2.（2017.11选考真题）某对分查找算法的VB程序段如下页图2所示，数组元素a（1）到a（7）的值依次为“24，35，38，41，45，69，78”。若该程序段执行后，文本框Text1中显示的内容可能是（   ）。

A.RL    B.LMR

C.RLR    D.LRLM

剖析：此题为对分查找过程分析题，key值未知，查找过程不唯一，不适用列表法求解，但分析题目发现本题可直接运用对分查找的特征结论来排除部分选项。

特征：①无论查找键key是否在被查找数组中，n个数的对分查找最多查找次数为int（log2n）+1。②如果查找键key在被查找数组中，n个数的对分查找最少查找次数为1次;如果查找键key不在被查找数组中，n个数的对分查找最少查找次数为int（log2n+1）。

分析程序可知，程序有两个结束出口：一是查找成功立即退出，字符串s以“M”结尾;二是查找不成功，字符串s中没有“M”。因此“M”不可能在字符串s中间，排除B选项;查找不成功时，对分查找最少要查找int（log2n+1）=3次，排除A选项;n个数的对分查找次数最多查找int（log2n）+1=3次，排除D选项。

点评：用对分查找算法的特征结论可以快速准确地完成试题分析，达到事半功倍的效果，对分查找算法还有如下3个特征：①如果查找键key在被查找数组中，则对分查找一定可以找到key，且查找结束时变量i，j的关系一定为i≤j。②如果查找键key不在被查找数组中，则对分查找结束时变量i，j的关系一定为i>j，且i=j+1。③如果查找键key不在被查找数组中，则对分查找结束时变量i，j一定指向与key值最接近的两个数。

● 巧用二叉树罗列查找分支

例3.（2020.1选考真题）某对分查找算法的VB程序段如图3所示。数组元素a（1）到a（10）的值依次为“2，3，5，8，9，10，13，17，19，20”。在文本框Text1中输入待查找的数，执行该程序段，则文本框Text2中显示的内容可能是（   ）。

A. 9  3

B. 9  3  5

C. 9  17  19  13

D. 9  3  5  8  19

剖析：此题为对分查找变形程序，查找成功时没有立即结束，一直进行到没有可查找区间（i>j）时结束，查找次数多。且查找键key值未知，查找过程不唯一，查找分支多，不适合用列表法解题。但只要画出二叉树模拟所有查找分支，就可快速解出此题，明确只有B选项符合。

点评：二叉树作为一种特殊的树形结构，是计算机科学领域中一种重要的数据结构。二叉树的树形结构刚好可以模拟出对分查找过程中依次访问到的中间位置元素，直观形象、条理清晰。所以，当遇到查找键key值未知，查找过程不唯一，需要考虑所有查找分支的试题时，用二叉树求解尤为方便快捷，解题效率会比列表法高。

● 善用数轴分析算法思路

例4.（2018.4选考真题）数组a为一组正整数，奇数在前，偶数在后。奇数与偶数已分别按升序排序。依据对分查找思想，设计一个在数组a中查找数据Key的程序。实现该功能的VB程序段如图4所示。程序中方框处可选语句为：①i=m+1，②j=m-1，③If Key

A.①、②、③    B.①、③、②

C.②、①、③    D.③、②、①

剖析：此题为对分查找算法在特殊数列中的应用。因为被查找数据是前奇后偶的两个升序段，且查找键key值未知，所以不能直接用标准对分查找程序进行对分查找，需要根据数据的特点分情况讨论来调整下一次的查找区间，本题可分三种情况来讨论分析：

情况1：如果查找键key为奇数，中间位置元素a（m）为偶数[Key Mod 2=1 And a（m） Mod 2=0]。因为奇数在前偶数在后，所以应调整下一次的查找区间为前半部分，即修改变量值j=m-1。

情况2：如果查找键key为偶数，中间位置元素a（m）为奇数[Key Mod 2=0 And a（m） Mod 2=1]。因为奇数在前偶数在后，所以调整下一次的查找区间为后半部分，即修改变量值i=m+1。

情况3：如果查找键key与中间位置元素a（m）的奇偶性一致，那么根据key值与a（m）的大小关系调整下一次的查找搜索区间。

点评：对分查找在特殊数列上应用的试题，强调考查学生的算法思维和算法分析能力，而算法分析正是教学中的重点也是难点内容。在算法分析过程中如果可以先使用图表画出数据特点，化抽象为具体，则可以使程序变得形象化、具体化。

本文以近几年选考卷中的对分查找算法试题为例，总结提出了4种针对对分查找算法问题的解题策略，并分析了不同解题策略所适用的试题题型。希望学生们在面对对分查找类试题时，可以灵活运用各种解题策略，迅速找到最合适的解题方法，准确高效地解出题目。但是试题千变万化，高中信息技术一线教师在平时的算法教学中，除了要让学生掌握解题策略，提高解题能力之外，更重要的是要让学生理解算法思想，建立算法思维，提高算法阅读能力和分析能力，培养计算思维能力，将信息技术学科的核心素养培养落到实处。