查找算法（课件）-高考信息技术一轮复习考点扫描（浙江专用）

专题二十二查找算法PART01顺序查找基本思想从第一个数据开始，按数据的顺序逐个将数据与给定的值进行比较。若某个数据和给定的值相等，则查找成功，找到所查数据的位置；反之，查找不成功。Key=Val(Text2.Text)

Fori=1Ton

Ifd(i)=KeyThenLabel5.Caption=“已找到，在数组的"+Str(i)+"位置"

ExitFor

EndIf

NextiIf

i=n+1

Then

Label5.Caption="在数组中没有找到"+Str(Key)EndIf程序代码

Key=Val(Text2.Text)

i=1

DoWhilei<=n

Ifd(i)=KeyThenLabel5.Caption=“已找到，在数组的"+Str(i)+"位置"

ExitDo

EndIf

i=i+1

LoopIfi=n+1Then

Label5.Caption="在数组中没有找到"+Str(Key)EndIfDO语句Key=Val(Text2.Text)k=0

Fori=1TonIfd(i)=KeyThenk=iExitFor

NextiIfk<>0Then

List1.Additem“已找到，在数组的”+Str(k)+“位置"Else

List1.Additem"在数组中没有找到"+Str(Key)EndIf变形1

Key=Val(Text2.Text)

i=1：Flag=0

DoWhilei<=nAndFlag=0

Ifd(i)=KeyThenLabel5.Caption=“已找到，在数组的"+Str(i)+"位置"

Flag=1

EndIf

i=i+1

LoopIfFlag=0Then

Label5.Caption="在数组中没有找到"+Str(Key)EndIf变形2PART02对分查找对分查找（二分查找），是一种效率很高的查找方法，但被查找的数据必须是有序的（以递增为例）基本思想：首先把待查数据与数组中间位置的数进行比较，如果待查数据比中间位置的数大，在数组的后半部分继续查找，否则在数组的前半部分查找，继续对分查找，直到找到待查数据在数组中的位置或数组已无法对分。基本思想1015171822273545485265677285979812345678910111213141516下标元素数组d(n):m=Int(

)=8i=1j=16第1次比较：Key>d(m)查找范围应该变成d(9)~d(16)Key=52我们用变量i和j记录所要查找范围的起始和终止位置(i+j)/2查找过程1015171822273545485265677285979812345678910111213141516下标元素i=9j=16第2次比较：Key<d(m)查找范围应该变成d(9)~d(11)我们用变量i和j记录所要查找范围的起始和终止位置数组d(n):Key=52m=Int(

)=12(i+j)/21015171822273545485265677285979812345678910111213141516下标元素i=9j=11第3次比较：Key=d(m)找到了我们用变量i和j记录所要查找范围的起始和终止位置数组d(n):Key=52m=Int(

)=10(i+j)/2

Key=Val(Text2.Text)i=1j=n

DoWhilei<=j

m=(i+j)\2Ifd(m)=KeyThenLabel6.Caption="在数组的"+Str(M)+"位置中"ExitSubEndIfIfd(m)<KeyThen

i=m+1Else

j=m-1EndIfLoopLabel6.Caption="在数组中没有找到"+Str(Key)程序代码

Key=Val(Text2.Text)

i=1：

j=n：Flag=False

DoWhilei<=jAndFlag=False

m=(i+j)\2Ifd(m)=KeyThenLabel6.Caption=“在数组的”+Str(M)+“位置中"

Flag=TrueElseIfd(m)<KeyThen

i=m+1Else

j=m-1EndIfLoopIfFlag=FalseThenLabel6.Caption=“在数组中没有找到"+Str(Key)变形注意点PART03方法便签解答技巧PART04典例分析【宁波十校】D【名校协作体】C【湖丽衢】D【杭州周边】某算法程序段如下:Dima(1To10)AsIntegerDimiAsInteger，jAsIntegerDimkeyAsSinglei=1:j=10:nx=0key=Int(Rnd*100)+0.5DoWhilei<=jm=(i+j)\2Ifkey=a(m)ThenExitDoElseIfkey<a(m)Thenj=m-1:nx=nx-1Elsei=m+1:nx=nx+1EndIfLoopText1.Text=Str(nx)已知数组元素a(1)至a(10)的值依次为11，26，37，49，55，62，78，79，85，98，若执行该程序后，文本框Text1中显示的内容不可能是（）A.-3 B.-1 C.3 D.4C某算法VB程序段如下：i=1:j=7:s=””key=int(rnd*100)Dowhilei<=jm=(i+j)\2Ifkey=a(m)thens=s+”M”ExitDo‘ExitDo表示退出循环ElseIfkey<a(m)thenj=m-1:s=s+”L”Elsei=m+1:s=s+”R”EndifLoopText1.Text=s数组a(1)到a(7)的值依次为”24、35、38、41、45、69、78”执行该程序段后，文本框text1显示的内容可能是()。A、RLB、LMRC、RLRD、LRLMC【杭州期末】D【绍兴卷】编写VB程序，实现把数据key插入到升序序列中，得到一个新的升序序列，原升序序列各元素已依次存放在数组元素a(1)、a(2)、a(3)、……、a(10)中，VB程序段如下：i=1:j=10DoWhilei<=jm=(i+j)\2Ifkey<=a(m)Then①Else②EndIfLoopFork=10ToiStep-1③Nextka(i)=key要使程序实现上述功能，则方框①②③中的语句分别是A．j=m–1i=m+1a(k+1)=a(k)B．j=m–1i=m+1a(k)=a(k–1)C．i=m+1j=m–

1a(k+1)=a(k)D．i=m+1j=m–1a(k)=a(k–1)A

【Z20名校联盟8月】下列程序段用于在前面部分为升序后面部分为降序的数组a中查找最大值，返回该数值及其位置（下标）。i=1:j=10flag=FalseDoWhilei<=jAndNotflagm=(i+j+1)\2Ifa(m)<a(m-1)Anda(m)>a(m+1)Then(1)ElseIfa(m)>a(m-1)Anda(m)>a(m+1)Then(2)ElseIfa(m)>a(m-1)Anda(m)<a(m+1)Then(3)EndIfLoopList1.AddItemStr(a(m))+Str(m)上诉程序方框处可选语句为：(1)i=m+1(2)j=m-1(3)flag=True则（1）、（2）、（3）处语句依次是A.(1)(2)(3) B.(1)(3)(2)C.(3)(1)（2）D.（2）（3）（1）D

D9（经典题，2分）某学校图书管理系统中有10万条图书资料记录（已经索引排序），假设从中取出一条记录并与待查项进行比较所花时间为10毫秒，则用对分查找法在该系统中查找任意一本指定图书最多花费的时间约为（）A.100万毫秒B.10万毫秒C.10毫秒D.170毫秒D小提示

n个数据，对分查找最多查找次数计算公式为Int(Log2n)+1，计算时难度较大，可以转换为2^x≈n,先找到2^x最接近n的x值，然后x+1即为最多查找次数,（建议记住这个等式：2^10=1024），例如有100000个数据，2^10*2^6即1024*64最接近100000，得出x值为16，则最多查找次数为16+1＝17次。10（2017浙江月考，2分）某对分查找算法的VB程序段如下：i=1：j=6：n=0：f=Falsekey=Val（Text1．Text）DoWhilei＜=jAndf=False n=n+1 m=（i+j）\2 If

key=d（m）Then

f=True If

key＜d（m）Then

j=m-1Else

i=m+1Loop数组元素d（1）到d（6）的值依次为“13，18，25，30，35，59”。文本框Text1中输入33后运行该程序，运行结束后下列说法不正确的是（）A.变量f的值为FalseB.变量i的值为5C.变量m的值为4D.变量n的值为2D11第18课第（5）题P110（2017.04浙江选考，3分）小王编写了一个实现文字查找替换功能的VB程序，运行界面如图所示。文本框Text1显示原文内容，Text2中输入查找内容，Text3中输入替换内容，单击“全部替换”按钮Command1后，Text4显示查找替换的结果，Text5中显示替换的次数，Text6显示“查找内容”在原文中的起始位置。12第18课第（5）题P110实现上述功能的VB程序如下，但加框处代码有错，请改正。PrivateSubCommand1_Click() DimsAsString,resultAsString,posAsString DimcountAsInteger,iAsInteger i=1:count=0 resule="":pos="" DoWhileI<=Len(Text1.Text) s=Mid(Text1.Text,i,Len(Text2.Text)) Ifs=Text2.TextThen result=result+Text3.Text count=count+1 pos=pos+Str(count) ′① i=i+Len(Text2.Text)第18课第（5）题P110 Else result=result+Text2.Text ′② i=i+1 EndIf Loop Text4.Text=result Text5.Text=