高考信息技术复习专题八-查找算法的程序实现

专题八查找算法的程序实现【考纲标准】考试内容考试要求查找算法的程序实现：①顺序查找②对分查找c1．(2018·11月浙江选考)数组a中存储的是左右交替上升的n个正整数，如下表所示：a(1)a(2)a(3)……a(n－2)a(n－1)a(n)32538……553112依据对分查找思想，设计一个在数组a中查找数据key的程序。实现该功能的VB程序如下，但加框处代码有错，请改正。EndIfEndSub解析本题考核对分查找的思想，算法比较简单，关键是对数组a中存储的是左右交替上升的n个正整数的理解，数组的前半部分是递增的，后半部分是递减的，且他们的大小变化规律是3→12→25→31→38→55。因此如果在前半部分找不到，还可能在右半部分对称的位置找到。因此(1)应修改为i<＝j，也就是说最后一次查找，变量i＝j＝m。如果在前半部分找不到，该数可能比a(m)小，此时j＝m－1，该数大于(j)但小于a(m)，在与j对称的位置(即n－j＋1)可能是要找的数；该数可能比a(m)大，此时i＝m＋1，该数大于a(m)但小于a(i)，在与(i－1)对称的位置(即n－(i－1)＋1)可能是要找的数。答案

(1)i＜＝j

(2)n－i＋2或n－j＋1或n＋1－(i＋j)2．(2018·11月浙江选考)数组a为一组正整数，奇数在前，偶数在后。奇数与偶数已分别按升序排序。依据对分查找思想：设计一个在数组a中查找数据Key的程序。实现该功能的VB程序段如下：i＝1:j＝10Key＝Val(Text1.Text)DoWhilei<＝jm＝(i＋j)\2Ifa(m)＝KeyThenExitDo′ExitDo表示退出循环IfKeyMod2＝1Anda(m)Mod2＝0Then①i＝m＋1②j＝

m－1③IfKey<a(m)Thenj＝m－1Elsei＝m＋1则(1)、(2)、(3)处语句依次是(

)A．①、②、③ B．①、③、②C．②、①、③ D．③、②、①解析本题考核对分查找算法。语句KeyMod2＝1Anda(m)Mod2＝0表示要查找的key是奇数，且m指向的数是偶数。奇数在前，向前找，移动尾指针。语句KeyMod2＝0Anda(m)Mod2＝1表示要查找的key是偶数，且m指向的数是奇数。答案C3．(2017·11月浙江选考)某算法的VB程序段如下：i＝1：j＝7：s＝""Key＝Int(Rnd*100)DoWhilei<＝jm＝(i＋j)\2IfKey＝a(m)Then

s＝s＋"M"：ExitDo

′ExitDo表示退出循环ElseIfKey<a(m)Then

j＝m－1：s＝s＋"L"Else

i＝m＋1：s＝s＋"R"EndIfLoopText1.Text＝s数组元素a(1)到a(7)的值依次为“24，35，38，41，45，69，78”。执行该程序段后，文本框Text1中显示内容可能的是(

)A．RL B．LMR C．RLR D．LRLM解析找到的情况下，显示M并停止查找，因此B选项是不可能的。7个数据，在找不到的情况下，至少查找的次数是Int(Log27)＋1＝3，因此A选项还需继续查找。D选项的查找次数超过了3次。第一次找到41，向右找，找到69，向左找，找到45，再向右找，没有找到，该数在(45，69)之间。答案C一、顺序查找1．查找是一种查询数据的技术，其目标是能以比较少的步骤或较短的时间找到所需的对象。2．顺序查找是在一个已知无(或有序)序队列中找出与给定关键字相同的数的具体位置。原理是让关键字与队列中的数从第一个开始逐个比较，直到找出与给定关键字相同的数为止。3．由于该部分在前面的几个专题均有练习，本专题不做专题讲述。二、对分查找 (一)基本算法思想

在一个升序或降序的数组中，确定该数组的开始位置i、结束位置j和中间位置m，用待查找的数key与m位置所在的值d(m)比较，如果相等，表示找到了，如果在前半段，把结束位置j修改为m－1，重新查找，如果在后半段，把开始位置i修改为m＋1，再次查找，直到找到或者开始位置大于结束位置为止。

中间位置m的计算公式：m＝Int((i＋j)/2)或者m＝(i＋j)\2或者m＝fix((i＋j)/2)。(二)核心代码1．在升序的数列d(1)至d(n)中查找key。用i表示开始位置下标，用j表示结束位置下标，m表示中间位置下标。若找到，输出该数据所在位置pos.如果pos＝0表示没有找到。 pos＝0:c＝0:i＝1:j＝n DoWhilei<＝j

′进入查找的条件，i与j的关系

m＝Int((i＋j)/2)

c＝c＋1

′表示查找次数

Ifd(m)＝KeyThenpos＝m

′找到，用xb记录下标位置ExitDo

′退出循环

ElseIfKey<d(m)Then

j＝m－1

Else

i＝m＋1

EndIfLoopIfpos＝0ThenText2.Text＝“找不到”ElseText2.Text＝“在数组中位置为”

＋Str(pos)＋“共查找了”

＋Str(c)＋“次”EndIf2．关于头尾指针移动有两种IF结构Ifd(m)＝KeyThen

pos＝m

′记录下标位置

ExitDo

′退出循环ElseIfKey<d(m)Then

j＝m－1Else

i＝m＋1EndIfIfd(m)＝KeyThen

pos＝m

′下标位置

ExitDo

′退出循环Else

IfKey<d(m)Then

j＝m－1

Else

i＝m＋1

EndIfEndIf3.根据pos变量的值判断结果，如果pos＝0，表示没有找到，否则输出查找位置pos。4．根据循环结束后变量i的值判断结果，如果没有找到，头指针i将移动到尾指针j的后面，即i>j；否则在中间位置找到，使用ExitDO语句中途退出，此时变量m表示查找位置。(三)查找过程1．明确i、j和m的含义，i表示开始位置，j表示结束位置，m表示[i，j]的中间位置。d(m)表示m这个位置所对应的数值。2．修改i、j的值，如果是升序系列，当要查找的数比中间的数d(m)小，表示要查找的数在前半段，让j＝m－1；否则在后半段，让i＝m＋1。如果是降序系列，则相反。3．结束查找有两个条件，中间m位置值d(m)与要查找的数key相等，或者是头指针i已经大于尾指针j。满足其中一个，就不再查找了。4．查找结束后，查找的结论是要查找的数在数组中位置m或者没有找到。(四)N个数最多的查找次数 N个数最多的查找次数最多的查找次数为Int(Log2N)＋1。(五)常用解题技巧1．列表法

用表格列出每次查找的区间和比较数的位置及值。2．二叉树法

假设有10个数据1、2、3、4、5、6、7、8、9、10②右2堆依次求出m值(2、8)，m值保留在原位，然后把2边数分别放入它的左右2个子树(小的放左子树，大的放右子树)；③节点里还有2个及以上数的，按照上面规则求m值，m值保留在原位，其他数放入它的左右2个子树(小的放左子树，大的放右子树)；④有左子树的往左画条线，代表往左查找失败的范围；没有右子树的往右画条线，代表往右查找失败的范围。【例1】

某对分查找算法的VB程序段如下：i＝1:j＝6:n＝0:f＝False：key＝Val(Text1.Text)DoWhilei<＝jandNotf

n＝n＋1m＝Fix((i＋j)/2)Ifkey＝a(m)Thenf＝TrueIfkey<a(m)Thenj＝m－1Elsei＝m＋1Loop数组元素a(1)到a(6)的值依次为“12，19，27，31，46，55”。文本框Text1中输入“30”后运行该程序，则以上程序段运行结束后，下列说法不正确的是(

)A．变量i的值为4 B．变量j的值为5

C．变量m的值为4 D．变量n的值为3解析本题考核的知识点是对分查找。可以用列表法进行跟踪变量。当i>j时，不再查找。答案Bijma(m)nflag163271False465462False444313False43

【变式训练1】

某对分查找算法的VB程序段如下：i＝1:j＝6:n＝0:f＝False：key＝Val(Text1.Text)DoWhilei<＝jandNotfn＝n＋1m＝Fix((i＋j)/2)Ifkey＝a(m)thenf＝TrueIfkey<a(m)thenj＝m－1Elsei＝m＋1Loop数组元素a(1)到a(6)的值依次为“12，19，27，31，46，55”。文本框Text1中输入“31”后运行该程序，则以上程序段运行结束后，下列说法不正确的是(

)A．变量i的值为4 B．变量j的值为5

C．变量m的值为4 D．变量n的值为3解析采用列表法进行分析。答案Bijma(m)fn16327False146546False244431True3【例2】

一组“非降序”的数据分别存储在数组元素a(1)……a(n)中，用对分查找算法在数组a中查找key值所在位置，如果有重复的元素，则显示最小的位置。部分VB程序如下：Key＝Val(Text1.Text)i＝1:j＝nDoWhilei<＝j

m＝(i＋j)\'2

Ifa(m)>KeyThen

j＝m－1

Elseifa(m)<KeyTheni＝m＋1

Else

If__________Thenj＝m－1

ElseLabel2.Caption＝Str(Key)＋

“的起始位置是”

＋Str(m):ExitDo

EndIfEndIfLoopIfi>jThenLabel2.Caption＝“找不到”

＋Str(Key)要使程序实现上述算法思想，则划线处的语句为(

)A．a(m－1)＝keyB．a(m)＝keyC．m－1>0anda(m－1)＝keyD．m－1>0anda(m)＝key解析要求如果有重复的元素，则显示最小的位置。即m不是第1个元素且a(m－1)＝key时，将尾指针移到m的前一个位置，继续查找。同时如果要取最后一个相同的数值。答案C【变式训练2】

某对分查找算法的VB程序段如下：L＝1:R＝10:Key＝21DoWhileL<＝Rm＝(L＋R)\2Ifa(m)<＝KeyThen

L＝m＋1

Else

R＝m－1Loop数组元素a(1)到a(10)的值依次为3，9，21，21，21，21，27，28，39，40，执行该程序段，变量R、a(R)的值分别是(

)A．2，9 B．3，21 C．6，21 D．7，27解析采用列表法进行分析。可见此时R指向的位置就是要查找的元素。答案CLRma(m)a(m)<＝Key？110521True610828False67621True77727False76

【例3】

某对分査找算法的VB程序段如下：Key＝Int(Rnd*100)i＝1:j＝7：s＝

""DoWhilei<＝jm＝(i＋j)\2IfKey＝a(m)Thens＝s＋

“M”：ExitDoIfKey<a(m)Thenj＝m－1:s＝s＋

“L”Elsei＝m＋1:s＝s＋

“R”EndIfLoopText1.Text＝sText1.Text＝s数组元素a(1)到a(7)的值依次为“25，36，39，42，47，66，78”，执行该程序段，文本框Text1中显示的内容是“RLR”，则可以确定随机产生的Key值范围是(

)A．(25，36) B．(47，66)C．(66，78) D．(78，100)解析画出对应的二叉树图如图所示，其中圈中所示数字均为元素在数组中位置。第一次查找，m的值为4，程序运行时，文本框Text1中显示的内容是“RLR”，即从第4个元素开