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

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

●勤用列表追踪查找过程

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

A.4024??B.402436

C.3624??D.361724

剖析：此题为对分查找过程分析题，查找键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的关系一定为ij，且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

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

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

●善用数轴分析算法思路

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

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

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

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

情况1：如果查找键key为奇数，中间位置元素a（m）为偶数[KeyMod2=1An