專題八查找算法的程序實現【考綱標準】考試內容考試要求查找算法的程序實現：①順序查找②對分查找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個元素開