查找算法（課件）-高考信息技術一輪復習考點掃描（浙江專用）

專題二十二查找算法PART01順序查找基本思想從第一個數(shù)據(jù)開始，按數(shù)據(jù)的順序逐個將數(shù)據(jù)與給定的值進行比較。若某個數(shù)據(jù)和給定的值相等，則查找成功，找到所查數(shù)據(jù)的位置；反之，查找不成功。Key=Val(Text2.Text)

Fori=1Ton

Ifd(i)=KeyThenLabel5.Caption=“已找到，在數(shù)組的"+Str(i)+"位置"

ExitFor

EndIf

NextiIf

i=n+1

Then

Label5.Caption="在數(shù)組中沒有找到"+Str(Key)EndIf程序代碼

Key=Val(Text2.Text)

i=1

DoWhilei<=n

Ifd(i)=KeyThenLabel5.Caption=“已找到，在數(shù)組的"+Str(i)+"位置"

ExitDo

EndIf

i=i+1

LoopIfi=n+1Then

Label5.Caption="在數(shù)組中沒有找到"+Str(Key)EndIfDO語句Key=Val(Text2.Text)k=0

Fori=1TonIfd(i)=KeyThenk=iExitFor

NextiIfk<>0Then

List1.Additem“已找到，在數(shù)組的”+Str(k)+“位置"Else

List1.Additem"在數(shù)組中沒有找到"+Str(Key)EndIf變形1

Key=Val(Text2.Text)

i=1：Flag=0

DoWhilei<=nAndFlag=0

Ifd(i)=KeyThenLabel5.Caption=“已找到，在數(shù)組的"+Str(i)+"位置"

Flag=1

EndIf

i=i+1

LoopIfFlag=0Then

Label5.Caption="在數(shù)組中沒有找到"+Str(Key)EndIf變形2PART02對分查找對分查找（二分查找），是一種效率很高的查找方法，但被查找的數(shù)據(jù)必須是有序的（以遞增為例）基本思想：首先把待查數(shù)據(jù)與數(shù)組中間位置的數(shù)進行比較，如果待查數(shù)據(jù)比中間位置的數(shù)大，在數(shù)組的后半部分繼續(xù)查找，否則在數(shù)組的前半部分查找，繼續(xù)對分查找，直到找到待查數(shù)據(jù)在數(shù)組中的位置或數(shù)組已無法對分?；舅枷?015171822273545485265677285979812345678910111213141516下標元素數(shù)組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記錄所要查找范圍的起始和終止位置數(shù)組d(n):Key=52m=Int(

)=12(i+j)/21015171822273545485265677285979812345678910111213141516下標元素i=9j=11第3次比較：Key=d(m)找到了我們用變量i和j記錄所要查找范圍的起始和終止位置數(shù)組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="在數(shù)組的"+Str(M)+"位置中"ExitSubEndIfIfd(m)<KeyThen

i=m+1Else

j=m-1EndIfLoopLabel6.Caption="在數(shù)組中沒有找到"+Str(Key)程序代碼

Key=Val(Text2.Text)

i=1：

j=n：Flag=False

DoWhilei<=jAndFlag=False

m=(i+j)\2Ifd(m)=KeyThenLabel6.Caption=“在數(shù)組的”+Str(M)+“位置中"

Flag=TrueElseIfd(m)<KeyThen

i=m+1Else

j=m-1EndIfLoopIfFlag=FalseThenLabel6.Caption=“在數(shù)組中沒有找到"+Str(Key)變形注意點PART03方法便簽解答技巧PART04典例分析【寧波十?！緿【名校協(xié)作體】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)已知數(shù)組元素a(1)至a(10)的值依次為11，26，37，49，55，62，78，79，85，98，若執(zhí)行該程序后，文本框Text1中顯示的內(nèi)容不可能是（）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表示退出循環(huán)ElseIfkey<a(m)thenj=m-1:s=s+”L”Elsei=m+1:s=s+”R”EndifLoopText1.Text=s數(shù)組a(1)到a(7)的值依次為”24、35、38、41、45、69、78”執(zhí)行該程序段后，文本框text1顯示的內(nèi)容可能是()。A、RLB、LMRC、RLRD、LRLMC【杭州期末】D【紹興卷】編寫VB程序，實現(xiàn)把數(shù)據(jù)key插入到升序序列中，得到一個新的升序序列，原升序序列各元素已依次存放在數(shù)組元素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要使程序?qū)崿F(xiàn)上述功能，則方框①②③中的語句分別是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名校聯(lián)盟8月】下列程序段用于在前面部分為升序后面部分為降序的數(shù)組a中查找最大值，返回該數(shù)值及其位置（下標）。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（經(jīng)典題，2分）某學校圖書管理系統(tǒng)中有10萬條圖書資料記錄（已經(jīng)索引排序），假設從中取出一條記錄并與待查項進行比較所花時間為10毫秒，則用對分查找法在該系統(tǒng)中查找任意一本指定圖書最多花費的時間約為（）A.100萬毫秒B.10萬毫秒C.10毫秒D.170毫秒D小提示

n個數(shù)據(jù)，對分查找最多查找次數(shù)計算公式為Int(Log2n)+1，計算時難度較大，可以轉(zhuǎn)換為2^x≈n,先找到2^x最接近n的x值，然后x+1即為最多查找次數(shù),（建議記住這個等式：2^10=1024），例如有100000個數(shù)據(jù)，2^10*2^6即1024*64最接近100000，得出x值為16，則最多查找次數(shù)為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數(shù)組元素d（1）到d（6）的值依次為“13，18，25，30，35，59”。文本框Text1中輸入33后運行該程序，運行結(jié)束后下列說法不正確的是（）A.變量f的值為FalseB.變量i的值為5C.變量m的值為4D.變量n的值為2D11第18課第（5）題P110（2017.04浙江選考，3分）小王編寫了一個實現(xiàn)文字查找替換功能的VB程序，運行界面如圖所示。文本框Text1顯示原文內(nèi)容，Text2中輸入查找內(nèi)容，Text3中輸入替換內(nèi)容，單擊“全部替換”按鈕Command1后，Text4顯示查找替換的結(jié)果，Text5中顯示替換的次數(shù)，Text6顯示“查找內(nèi)容”在原文中的起始位置。12第18課第（5）題P110實現(xiàn)上述功能的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=