第三單元 查找算法

第三單元查找算法夯實(shí)考點(diǎn)考點(diǎn)1順序查找1.查找算法所謂查找就是在指定的數(shù)據(jù)中尋找某一特定的數(shù)據(jù)。查找結(jié)果有兩種,找到(查找成功)和未找到(查找失敗)。2.順序查找的基本思想從第一個(gè)數(shù)據(jù)開始,從左往右(或從上到下)將數(shù)據(jù)按順序逐個(gè)與給定的關(guān)鍵字進(jìn)行比較,若某個(gè)數(shù)據(jù)和給定的關(guān)鍵字相等,則查找成功,找到并輸出第一個(gè)與關(guān)鍵字相等的數(shù)據(jù)的位置;反之,查找失敗。若有n個(gè)數(shù),則可能的最多查找次數(shù)為n。3.順序查找算法基本框架假設(shè):要查找的數(shù)為key,待查找的數(shù)存放在數(shù)組d中。For語句框架:

Fori=1ton若d(i)=key,則表示找到,做相應(yīng)處理

Nexti若i>n表示未找到DoWhile語句框架:

i=1

Dowhilei<=n若d(i)=key,則表示找到,做相應(yīng)處理

i=i+1

Loop若i>n表示未找到4.順序查找的程序?qū)崿F(xiàn)在n個(gè)數(shù)組元素中依次查找,找到第1個(gè)滿足條件的值,查找即結(jié)束,輸出找到元素所在的位置;若找不到,輸出“未找到”。程序?qū)崿F(xiàn):設(shè):(1)要查找的數(shù)據(jù)是key(在文本框Text1中輸入),查找的數(shù)據(jù)存放在數(shù)組d中。(2)pos為找到數(shù)的位置,pos=0表示未找到。(3)p記錄查找的次數(shù)。key=Val(Text1.Text)

'Val要根據(jù)實(shí)際情況決定是否要添加

p=0

pos=0

find=False

'find=False表示未找到,find=True表示找到

i=1

DoWhilei<=nAndfind=False

'表示還沒找完并且還未找到,則繼續(xù)查找,notfind也可表示為find=False

p=p+1

Ifkey=d(i)Then

pos=i

find=True

EndIf

i=i+1

Loop

IffindThen'也可表示為Iffind=TrueThen

Text2.Text="在d("+Str(pos)+")中"

Else

Text2.Text="未找到"

EndIf典例1

某查找算法的部分VB代碼如下:t=Falsei=0DoWhilei<7Andt=False

i=i+1

Ifa(i)=keyThent=TrueLoopIft=FalseTheni=0數(shù)組元素a(1)到a(7)的數(shù)據(jù)依次為“3,5,1,5,8,9,5”,當(dāng)變量key值為5時(shí),運(yùn)用該算法處理后,變量i的值是(

)A.0 B.2 C.4 D.7解析:本題主要考查的是順序查找的實(shí)現(xiàn)過程。本程序的功能是查找數(shù)組中第一個(gè)與目標(biāo)數(shù)據(jù)相等的數(shù),若找到將其在數(shù)組中的位置賦給變量i,結(jié)束查找;若找不到,變量i=0。因?yàn)槟繕?biāo)值key=5,它和數(shù)組中第二個(gè)數(shù)正好相等,因此i=2。答案:B典例2編寫一個(gè)VB程序,實(shí)現(xiàn)如下功能:在列表框List1中顯示十個(gè)字符串,十個(gè)字符串存放在數(shù)組s中,在文本框Text1中輸入一個(gè)字符串,單擊“統(tǒng)計(jì)”按鈕,統(tǒng)計(jì)字符串出現(xiàn)的次數(shù),若出現(xiàn)次數(shù)大于0,則在文本框Text2中顯示實(shí)際次數(shù),若出現(xiàn)次數(shù)為0,則在文本框Text2中顯示“找不到”。程序運(yùn)行效果如圖3-1所示。為實(shí)現(xiàn)上述功能,請(qǐng)?jiān)诔绦騽澗€處填入合適的語句:程序①處語句為

;

程序②處語句為

;

程序③處語句為

。

解析:要查找的字符為st,st通過文本框Text1中輸入得到,因此①處語句為Text1.Text;將要查找的字符串按順序與數(shù)組s中元素比較,如果相等,則進(jìn)行計(jì)數(shù),因此②處語句為s(i)=st;根據(jù)題目“若出現(xiàn)次數(shù)大于0,則在文本框Text2中顯示實(shí)際次數(shù),若出現(xiàn)次數(shù)為0,則在文本框Text2中顯示“找不到”?？芍厶幍恼Z句為num>0或num<>0。答案:①Text1.Text②s(i)=st③num>0或num<>0典例3

某6位學(xué)生的學(xué)號(hào)存儲(chǔ)在數(shù)組元素a(1)到a(6)中,其數(shù)據(jù)依次為“2015001,2015003,2015078,2015010,2015788,2015666”。使用順序查找算法查找學(xué)號(hào)2015700,則共需查找次數(shù)為(

)A.0 B.5 C.6 D.7解析:本題考查的是順序查找算法的實(shí)現(xiàn)過程。由于給定的數(shù)組中沒有數(shù)據(jù)2015700,因此需要與數(shù)組中每個(gè)數(shù)進(jìn)行比較,因此共需查找次數(shù)為6次。答案:C考點(diǎn)2對(duì)分查找1.對(duì)分查找的基本思想在有序的數(shù)據(jù)序列中(一般存放在數(shù)組中),首先把要查找的數(shù)據(jù)與數(shù)組中間位置的元素進(jìn)行比較,如果相等,則查找成功并退出查找;否則,根據(jù)數(shù)組元素的有序性,確定數(shù)據(jù)應(yīng)在數(shù)組的前半部分還是在后半部分查找;在確定了新的查找范圍后,重復(fù)進(jìn)行以上比較,直到找到或未找到為止?！局仉y點(diǎn)剖析】①對(duì)分查找的前提是被查找的數(shù)據(jù)序列必須是有序。②“未找到”是指當(dāng)指定范圍內(nèi)的起點(diǎn)大于終點(diǎn)仍未找到該數(shù)據(jù)。2.對(duì)分查找算法基本框架說明:要查找的數(shù)為key,待查找的數(shù)存放在數(shù)組d中。

i為查找范圍的起點(diǎn),j為查找范圍的終點(diǎn),m為范圍[i,j]的中間位置。

i=1

j=n

DoWhilei<=j計(jì)算中點(diǎn)位置m比較key與d(m),并做相應(yīng)處理

Loop若i>j,則表示未找到3.對(duì)分查找程序?qū)崿F(xiàn)在n個(gè)數(shù)組元素中依次查找,找到第1個(gè)滿足條件的值,查找就結(jié)束,輸出找到元素所在的位置;若找不到,輸出“未找到”。程序?qū)崿F(xiàn):設(shè)要查找的數(shù)據(jù)是key(在文本框Text1中輸入),查找的數(shù)據(jù)存放在數(shù)組d中。在文本框Text2中輸出查找結(jié)果,若找到輸出“找到!位置為:X”,否則輸出“未找到!”在文本框Text3中輸出共查找的次數(shù)。p表示查找的次數(shù)。核心代碼為(以升序?yàn)槔?:key=Val(Text1.Text)

′表示要查找的數(shù)

p=0

′表示查找的次數(shù)

find=False

′查找的結(jié)果,若find=True表示找到,find=False表示未找到

i=1

′查找范圍的起點(diǎn)

j=n

′查找范圍的終點(diǎn)

DoWhilei<=jAndNotfind

′如果還未找完并且未找到

p=p+1

′查找次數(shù)計(jì)數(shù)

m=(i+j)/2

′計(jì)算中點(diǎn)位置m

Ifkey=d(m)Then

′表示找到的情況

find=True

Text2.Text="找到!位置為:"+Str(m)

EndIf

Ifkey>d(m)Then

′表示查找的數(shù)比中間位置上的數(shù)大時(shí)

i=m+1

Else

′表示查找的數(shù)比中間位置上的數(shù)小時(shí)

j=m-1

EndIfLoop

IfNotfindThenText2.Text="未找到!"Text3.Text="共查找的次數(shù)為:"+Str(p)【重難點(diǎn)剖析】計(jì)算中點(diǎn)位置的語句還可以寫成:m=Int((i+j)/2)或m=Fix((i+j)/2)。典例4(2015浙江省10月選考題)已知單調(diào)函數(shù)在[0,1]區(qū)間存在一個(gè)x0,使f(x0)=0。現(xiàn)用對(duì)分查找算法搜索x0的值,開始搜索區(qū)間為[0,1],若經(jīng)過10次對(duì)分查找后還需繼續(xù)搜索,則第11次搜索區(qū)間的長(zhǎng)度為(

)A.1/2 B.1/10 C.1/102 D.1/210解析:本題主要考查的是對(duì)分查找算法。在[0,1]區(qū)間內(nèi)查找一個(gè)數(shù),第一次取[0,1]區(qū)間中間值0.5,如果f(0.5)<0,則第二次區(qū)間為[0.5,1],如果f(0.5)>0,則第二次區(qū)間為[0,0.5],每次都減少為原來的1/2,所以答案為D。答案:D典例5a數(shù)組(a(1)～a(8))中存儲(chǔ)了8本圖書的價(jià)格,其數(shù)據(jù)依次為“105,98,95,60,55,35,12,8”?，F(xiàn)使用對(duì)分查找數(shù)據(jù)8,需要查找的次數(shù)是(

)A.1 B.2 C.3 D.4解析:本題主要考查的是對(duì)分查找算法的實(shí)現(xiàn)過程。根據(jù)計(jì)算公式m=(i+j)/2可知,第一次訪問的數(shù)據(jù)為60(第4個(gè)),第二次訪問的數(shù)據(jù)為35(第6個(gè)),第三次訪問的數(shù)據(jù)為12(第7個(gè)),第四次訪問的數(shù)據(jù)為8(第8個(gè)),因此答案為D。答案:D典例6某數(shù)組有10個(gè)數(shù)據(jù),依次為1,2,3,4,5,6,7,8,9,10,現(xiàn)要查找某一數(shù)據(jù),若使用對(duì)分查找目標(biāo)數(shù)據(jù),需查找兩次,若用順序查找需查找8次,則要查找的目標(biāo)數(shù)據(jù)為(

)A.2 B.3 C.7 D.8解析:本題考查的是兩種查找算法。根據(jù)順序查找次數(shù)即可判定目標(biāo)數(shù)據(jù)為8,我們?cè)儆脤?duì)分查找進(jìn)行驗(yàn)證,第一次查找的位置是m=(1+10)/2=5,第二次查找的位置是m=(6+10)/2=8,第8個(gè)位置上的數(shù)就是8,因此答案為D。答案:D典例7小明編寫了一個(gè)學(xué)生IC卡余額查詢系統(tǒng),其功能是在文本框Text1中輸入學(xué)生的IC卡號(hào),單擊“查詢余額”按鈕Command1后,在標(biāo)簽Label3中輸出查找結(jié)果。程序運(yùn)行效果如圖3-2所示。程序說明:(1)學(xué)生的IC卡號(hào)保存在數(shù)組card中,并已按升序排序好;卡中金額保存在數(shù)組money中。例:第i個(gè)學(xué)生的卡號(hào)保存在card(i)中,其對(duì)應(yīng)的金額保存在money(i)中。(2)如果在數(shù)據(jù)庫中找到此卡號(hào),則在標(biāo)簽Label3中顯示“此卡號(hào)余額為”及對(duì)應(yīng)的余額,如果未找到則顯示“查無此號(hào)!”。(3)程序運(yùn)行,將在左邊列表框List1中顯示學(xué)生的卡號(hào)和金額。解決此問題的部分程序段如下:Constn=1500

′設(shè)共有n張卡Dimcard(1Ton)AsLongDimmoney(1Ton)AsSinglePrivateSubForm_Load()

′此過程用于輸入卡號(hào)及金額,并存儲(chǔ)在數(shù)組card和money中代碼略EndSubPrivateSubCommand1_Click()DimxAsLong,iAsLong,jAsLong,mAsLong,findAsBooleanx=Val(Text1.Text)i=1

①

find=False

DoWhile②

m=(i+j)/2

Ifx=card(m)Then

③

ElseIfx<card(m)Then

j=m-1

Else

i=m+1

EndIfLoopIffind=TrueThen

Label3.Caption="此卡號(hào)余額為"+④+"元"

Else

Label3.Caption="查無此號(hào)!"

EndIfEndSub(1)解決此問題的算法是

。(選填:對(duì)分查找或順序查找)

(2)在程序①,②,③,④劃線處填入適當(dāng)?shù)恼Z句或表達(dá)式,將程序補(bǔ)充完整:程序中①劃線處應(yīng)填入

。

程序中②劃線處應(yīng)填入

。

程序中③劃線處應(yīng)填入

。

程序中④劃線處應(yīng)填入

。

解析:本題考查的是對(duì)分查找算法的程序?qū)崿F(xiàn)。對(duì)分查找的關(guān)鍵在于確定每次查找的范圍,程序用變量i,j表示查找的范圍,根據(jù)劃線①處前面的語句可以確定①處的語句應(yīng)表示首次查找范圍的終點(diǎn),即j=n;劃線②處的語句表示查找的條件,如果還沒找完并且還