資源簡介

第4節　查找算法

考試內容 考試要求
順序查找算法思想及程序實現 c
對分查找算法思想及其變形的程序實現 c

一、順序查找算法思想和程序實現
順序查找的基本思想是從第一個數據開始，按順序逐個將數據與給定的數據(查找鍵)進行比較，若某個數據和查找鍵相等，則查找成功，輸出所查數據的位置；反之，輸出未找到。

For i ＝ 1 To n If a(i)＝key Then 　Exit For End If Next i 代碼分析：將數組中的每個元素逐個與key進行比較，如果相等則查找成功，循環結束。如果循環結束后，變量i的值等于n＋1，則意味著沒有找到。順序查找數組可以無序
二、對分查找算法思想
對分查找又稱二分查找，是一種高效的查找方法。對分查找的前提是被查找的數據是有序的(升序或降序)。對分查找的基本思想是在有序的數列中，首先將要查找的數據與有序數列內處于中間位置的數據進行比較，如果兩者相等，則查找成功；否則就根據數據的有序性，再確定該數據的范圍應該在數列的前半部分還是后半部分；在新確定的縮小范圍內，繼續按上述方法進行查找，直到找到要查找的數據，即查找成功，如果要查找的數據不存在，即查找不成功。
若key為查找關鍵字，數組d存放n個已按升序排序的數據。使用對分查找時，把查找范圍[i，j]的中間位置上的數據d(m)與key進行比較，結果必然是如下三種情況之一：
(1)若key(2)key＝d(m)，找到了需要的數據；
(3)key>d(m)，查找鍵大于中點d(m)處的數據。由數組d中的數據的遞減性，可以確定：在(i, m)內不可能存在值為key的數據，必須在新的范圍(m＋1，j)中繼續查找。
這樣，除了出現情況(2)，在通過一次比較后，新的查找范圍將不超過上次查找范圍的一半。
數組d為例，觀察對分查找的過程。要查找的數據key＝52，查找過程如下：

三、對分查找算法代碼實現

i ＝ 1: j ＝ n: s ＝ 0 Do While i <＝ j 　 m ＝ (i ＋ j) \ 2 　 If a(m) ＝ key Then 　 s ＝ m: Exit Do 　 ElseIf key < a(m) Then 　 j ＝ m － 1 　 Else 　 i ＝ m ＋ 1 　 End If Loop 左邊程序實現在升序數組a(1)…a(n)中查找值等于key的元素，將其下標存儲在s中。如果沒有找到則s值為0，如果找到，則s存儲對應元素的下標。 對分查找前提是數據有序，對n個數據查找，最多查找次數為Log2n＋1(向下取整)。 例如在有序數組a(1)…a(10000)中查找某個值，最多需要查找Log210000＋1，即14次


一、順序查找算法思想和代碼實現
【典例1】 小王拿著一大串鑰匙去開倉庫的某一扇門，由于鑰匙上沒有任何標記，小王只能將這一串鑰匙一把一把地去試，從算法角度看，小王的做法屬于(　　)
A.冒泡排序 B.選擇排序
C.對分查找 D.順序查找
解析　本題考查兩個算法的區別。順序查找的思想第從第一個數據開始，按數據的順序逐個將數據與給定的值進行比較，若某個數據與給定的值相等，則查找成功，否則查找不成功。
答案　D
【變式訓練】 用對分查找法和順序查找法在數字序列“1，2，3，5，8，13，21，34，55”中查找數字13，兩種方法都能訪問到的數字是(　　)
A.3 B.5
C.8 D.34
解析　對分查找訪問到的數字為8、21、13，順序查找訪問到的數字為1，2，3，5，8，13。兩者共同為8。
答案　C
二、對分查找算法思想
【典例2】 已知單調函數f(x)在[0，1]區間存在一個x0，使f(x0)＝0。現用對分查找法搜索x0的值，開始搜索區間為[0，1]，若經過10次對分查找后還需繼續搜索，則第11次搜索區間的長度為(　　)
A.1/2 B.1/10
C.1/102 D.1/210
解析　對分查找的每次區間變為上次的二分之一。第2次為原搜索區間的長度1/2，第3次為原搜索區間的長度1/4……第11次為原搜索區間的長度1/210，所以答案D。
答案　D
【變式訓練】 下列有關查找的說法，正確的是(　　)
A.進行對分查找時，被查找的數據必須已按升序排列
B.進行對分查找時，如果查找的數據不存在，則無需輸出結果
C.在新華字典中查找某個漢字，最適合使用順序查找
D.對規模為n的數據進行順序查找，平均查找次數是
解析　對分查找的前提是被查找的數據是有序的(升序或降序)。如果找不到，程序應該要輸出未找到的相關提示信息。在新華字典中查找某個漢字，不適合使用順序查找，適合使用對分查找。對規模為n的數據進行順序查找，最少查找1次，最多查找n次，平均查找次數是。
答案　D
【典例3】 數組變量d(1)到d(8)的值依次為97、86、79、68、56、41、33、13，用“對分查找”找到“13”的過程中，依次被訪問到的數據是(　　)
A.68、13 B.68、41、13
C.56、41、33、13 D.68、41、33、13
解析　本題考查標準的對分查找，查找中間項為m＝(i＋j)\2，經過4次對分查找。

i 1 5 7 8
j 8 8 8 8
m 4 6 7 8
d(m) 68 41 33 13
答案　D
【變式訓練】 在有序單詞序列“bike，cake，data，easy，feel，great，hive，mark，sweet”中，用對分查找算法找到“easy”過程中，依次被訪問到的數據為(　　)
A.feel, data, easy
B.great, data, easy
C.bike, cake, dada，easy
D.feel，cake，data，easy
解析　本題考查標準的對分查找，查找中間項為m＝(i＋j)\2，經過4次對分查找。

i 1 1 3 4
j 9 4 4 4
m 5 2 3 4
d(m) feel cake data easy
答案　D
三、對分查找算法代碼實現
【典例4】 某對分査找算法的VB程序段如下：
i ＝ 1: j ＝ 9: n ＝ 0
key ＝ Val(Text1.Text)
Do While i <＝ j
　n ＝ n ＋ 1
　m ＝ Fix((i ＋ j) / 2)
　If key ＝ d(m) Then Exit Do　′Exit Do表示退出循環
　If key < d(m) Then j ＝ m － 1 Else i ＝ m ＋ 1
Loop
數組元素d(1)到d(9)的值依次為“7，12，18，25，39，58，61，72，86”。若該程序段運行結束后，n的值為2，則key的值是(　　)
A.39 B.18或61
C.18或72 D.12或61
解析　n代表查找次數，代入選項計算查找次數為2，即為答案。key＝12，第1次：m＝5，i＝1，j＝4；第2次：m＝2 ，d(m)＝12查找成功。key＝61，第1次：m＝5，i＝6，j＝9；第2次：m＝7 ，d(m)＝61查找成功。所以答案選D。
答案　D
【變式訓練】 采用如下對分查找算法對數組a中7個有序數據“15，38，51，66，77，81，99”進行查找，查找數據為“55”，
i ＝ 1: j ＝ 7: x ＝ 55
Do While i <＝ j
m ＝ (i ＋ j) \ 2
If a(m) ＝ x Then Exit Do
If a(m) > x Then j ＝ m － 1 Else i ＝ m ＋ 1
Loop
執行完上述代碼后，根據最終變量值判斷下列表達式，其中正確的是(　　)
A.i＝m＋1 B.i＝m－1
C.j>m＋1 D.j解析　本題考查標準的對分查找，查找中間項為m＝(i＋j)\2，最終沒有找到該數據。算法結束時i＝4，j＝3，m＝3，所以答案選A。

i 1 1 3 4
j 7 3 3 3
m 4 2 3
d(m) 66 38 51
答案　A
【典例5】 有如下VB程序段：
i ＝ 1 : j ＝ 10 : flag ＝ True : n ＝ 0
Key ＝ Val(Text1.Text)
Do While i <＝ j And flag ＝ True
m ＝ (i ＋ j) \ 2
If a(m) ＝ Key Then
flag ＝ False
ElseIf a(m) > Key Then
i ＝ m ＋ 1 : n ＝ n － 1
Else
j ＝ m － 1 : n ＝ n ＋ 1
End If
Loop
數組元素a(1)到a(10)依次是99, 94, 90, 87, 70，69，60，56，45，36，變量n的值最終是0，則文本框Text1輸入的數字可能是(　　)
A.100 B.87
C.69 D.41
解析　本題考查的是對分查找的變形。當key＝100時，程序執行過程中，各個變量的值變化情況如下表所示：

i 1 1 1 1
j 10 4 1 0
m 5 2 1
d(m) 70 94 99
n 1 2 3
當key＝87時，程序執行過程中，各個變量的值變化情況如下表所示：

i 1 1 3 4
j 10 4 4 4
m 5 2 3 4
d(m) 70 94 90 87
n 1 0 －1
當key＝69時，程序執行過程中，各個變量的值變化情況如下表所示：

i 1 6 6
j 10 10 7
m 5 8 6
d(m) 70 56 69
n －1 0
當key＝41時，程序執行過程中，各個變量的值變化情況如表所示。

i 1 6 9 10 10
j 10 10 10 10 9
m 5 8 9 10
d(m) 70 56 45 36
n －1 －2 －3 －2
答案　C
【變式訓練】 有如下VB程序段：
i ＝ 1: j ＝ 9: f ＝ False
Do While i <＝ j And Not f
m ＝ Fix((i ＋ j) / 2)
If a(m) ＝ Key Then
p ＝ m : f ＝ True
End If
If a(m) > Key Then
j ＝ m － 1
Else
i ＝ m ＋ 1
End If
Loop
If f ＝ True Then
　 Text1.Text＝“數據位置：” ＋ Str(p)
Else
　Text1.Text＝“沒有找到該數據！”
End If
數組元素a(1)到a(9)的值依次為10，15，30，32，38，42，45，48，68，若通過如下程序段查找數據key＝43，則在執行該程序段的過程中，依次訪問的數據是(　　)
A.38，45，42 B. 38，45，48
C.38，48，42 D. 38，48，45
解析　本題考查的是對分查找的變形。在程序執行過程中，各個變量的值變化情況如下表所示，所以答案選A。

i 1 6 6
j 9 9 6
m 5 7 6
d(m) 38 45 42
答案　A
【典例6】 小明為了研究對分查找的過程中數據被訪問的情況，編寫了一個VB程序，功能如下：在列表框List1中顯示已經排序的數據(存儲在數組a中)，在文本框Text1中輸入要查找的數據，單擊“查找”按鈕Command1后，在標簽Label1中顯示查找中依次被訪問到的數據。程序運行界面如圖所示。

實現上述功能的VB程序如下，但加框處代碼有錯，請改正。
Const n ＝ 10
Dim a(1 To n) As Integer
Dim s As String
Private Sub Form_Load()
′產生隨機數依次存儲在數組a中，代碼略
′對數組a升序排序并在列表框輸出，代碼略
End Sub
Private Sub Command1_Click()
　Dim x As Integer, p As Integer
　x ＝ Val(Text1.Text)
　s ＝ “ ”
　 　　　　′(1)
　If p > 0 Then s ＝ s ＋ “查找成功” Else s ＝ s ＋ “查找失敗”
　Label1.Caption ＝ “依次被訪問的數據為：” ＋ s
End Sub
Function search(key As Integer) As Integer
　Dim i As Integer, j As Integer, flag As Boolean
　flag ＝ False
　i ＝ 1: j ＝ n: search ＝ 0
　Do While i <＝ j And Not flag
m ＝ (i ＋ j) \ 2
If a(m) ＝ key Then
　 search ＝ m
　 flag ＝ True
　　　　 ′(2)
　 j ＝ m － 1
Else
　 i ＝ m ＋ 1
End If
s ＝ s ＋ Str(a(m)) ＋ “→”
　Loop
End Function
程序中加框(1)處應改正為_________________________________________；
加框(2)處應改正為________________________________________________。
解析　(1)聯系下文代碼If p > 0 Then，需要對變量p賦值，結合函數search的功能：如果在數組a中找到要查找的數，函數search 返回該數在數組中的位置，如果沒有找到，函數search 返回值為0，結合程序得知第1空為：p＝search(x)。
(2)在一個塊If語句中結合對分查找算法得出第2空為： ElseIf Key < a(m) Then。
答案　(1)p＝search(x)　(2)ElseIf Key < a(m) Then

1.某數組有10個元素，依次為：5，12，16，23，27，30，35，41，49，50。下列說法正確的是(　　)
A.使用對分查找數據12，需要的查找次是3次
B.使用順序查找數據50，需要的查找次數是9次
C.使用對分查找數據41，需要的查找次數是2次
D.使用順序查找數據5，需要的查找次數是0次
解析　本題考查標準的對分查找，查找中間項為m＝(i＋j)\2，查找12的過程如下表所示。故查找12需要2次。

i 1 1
j 10 4
m 5 2
d(m) 27 12
順序查找數據50，需要的查找次數是10次，
查找41的過程如下表所示，故查找41需要4次。

i 1 6
j 10 10
m 5 8
d(m) 27 41
順序查找5需要1次。
答案　C
2.某對分查找算法的VB程序段如下：
i＝1：j＝7：n＝0：f＝False
Key＝Val(Text1.Text)
Do While i<＝j　And　f＝False
n＝n＋1
m ＝ Fix((i ＋ j) / 2)
If　Key＝d(m)　Then f＝True
If　KeyLoop
元素d(1)到d(7)的值依次是“10，20，30，40，50，60，70”，文本框Text1中輸入35后運行程序段，運行結束后下列說法正確的是(　　)
　　　　　　　　　　　　　　　　　　

A.變量f的值是True B.變量i的值是4
C.變量m的值是3.5 D.變量n的值是4
解析　本題考查的是對分查找的變形。在程序執行過程中，各個變量的值變化情況如下表所示：
i 1 1 3 4
j 7 3 3 3
n 1 2 3
m 4 2 3
f false false false
d(m) 40 20 30
程序執行后，變量i＝4，變量j＝3，變量n＝3，變量m＝3，變量f＝false。
答案　B
3.某對分查找算法的VB程序段如下：
n ＝ 0: i ＝1: j ＝6
Key ＝ Val(Text1.Text)
f ＝ False
Do While i < ＝ j And Not f
　m ＝ (i ＋ j ＋1) \ 2
　n ＝ n ＋ 1
　If Key ＝ d (m) Then
f ＝ True
　ElseIf Key > d(m) Then
j＝m－1
　Else
i＝m＋1
　End If
Loop
數組元素d(1)到d(6)的值依次為“87，72，53，41，29，18”，若該程序段運行后，n的值為2，則key的值是(　　)
A.87或29 B.72或18
C.72或29 D.53或18
解析　本題考查對分查找的變形，n代表查找次數，n＝2代表查找次數是2次。第一次查找：i＝1，j＝6，m＝4，d(m)＝41。第二次查找分為兩種情況，第一種情況是key<41，i＝1，j＝3，m＝2，d(m)＝72；第二種情況是key>41，i＝5，j＝6，m＝6，d(m)＝18，所以答案是B。
答案　B
4.某對分査找算法的VB程序段如下：
i ＝ 1: j ＝ 7: s ＝ “ ”
key ＝ Int(Rnd * 100)
Do While i <＝ j
　 m ＝ (i ＋ j) \ 2
　 If key ＝ a(m) Then
　 s ＝ s ＋ “M”： Exit Do　′Exit Do 表示退出循環
　 ElseIf key < a(m) Then
　 j ＝ m － 1: s ＝ s ＋ “L”
　 Else
　 i ＝ m ＋ 1: s ＝ s ＋ “R”
　 End If
Loop
Text1.Text ＝ s
數組元素a(1)到a(7)的值依次為“24，35，38，41，45，69，78”。若該程序段執行后，文本框Text1中顯示的內容可能是(　　)
A.RL B.LMR
C.RLR D.LRLM
解析　本題主要考查對分查找的變形和查找次數，最簡單的方法是使用排除法。分析程序可知，查找成功則會輸出“M”，循環結束，所以“M”不可能出現在中間，排除B選項。對于n個數據查找，最多的查找次數是Log2n＋1(向下取整)，7個元素最多只需要查找3次，所以排除D選項，如果無法找到數據，則不會輸出“M”，則需要查找的次數是3次，所以排除A選項。
答案　C
5.數組a中有100個正整數，已按升序排列。在文本框Text1中輸入一個正整數key，尋找數組a中是否有一對數的和等于給定的數key。若存在和為key的數對，輸出該數對包含的兩個整數，小的在前，大的在后。若有多個數對滿足條件，則輸出最先找到的數若找不到符合要求的數對，則輸出“沒有符合條件的數對”。小吳為此編寫了VB程序，代碼如下，但加框處代碼有錯，請改正。
Dim a(1 To 100) As Integer
Const n ＝ 100
Private Sub Command1_C1ick()
Dim key As Integer, left As Integer, right As Integer, mid As Integer
Dim flag As Boolean
flag ＝ False: key ＝ Val(Text1.Text)
For i ＝ 1 To n － 1
　　　　　 ′①
right ＝ n
Do While 　　　　　　　　 ′②
mid ＝ (left ＋ right)\2
If a(i)＋a(mid) < key Then
　　　　left ＝ mid ＋ 1
ElseIf a(i)＋a(mid) > key Then
　　　　right ＝ mid－1
Else
　　　　List1.AddItem Str(a(i)) & “ ” & Str(a(mid))
　　　　flag ＝ True
End If
Loop
Next i
If Not flag Then Listl.AddItem “沒有符合條件的數對”
End Sub
程序中加框①處應改正為____________________________________________；
加框②處應改正為___________________________________________________。
解析　i＝1時，從a(2)到a(100)里面查找a(mid)，使a(1)＋a(mid)等于key。在a(2)到a(50)之間采用對分查找如果找到，輸出，Flag變為True，循環結束。否則繼續……i＝2時，從a(3)到a(50)里面查找a(mid)，使a(2)＋a(mid)等于key。
答案　①left＝i＋1　②left<＝right And Not Flag

基礎鞏固

1.下列關于數列查找說法，正確的是(　　)
A.使用對分查找，數列中每個元素對象不能是字符串類型的數據
B.使用對分查找數列，數列中每個元素要求必須是經過排序的
C.對于規模為1000萬項數的數列，不能使用順序查找
D.使用順序查找，只能從第1個元素依次向后進行查找
解析　對分查找的前提是被查找的數據是有序的(升序或降序)，數據類型可以使數字類型也可以是字符串類型。順序查找可以從第一個數據依次往后查找，也可以從最后一個數據依次向前查找。
答案　B
2.某對分査找算法的VB程序段如下：
i ＝ 1: j ＝ 9: f ＝ False
Do While i <＝ j And Not f
m ＝ Fix((i ＋ j) / 2)
If a(m) ＝ Key Then
p ＝ m : f ＝ True
End If
If a(m) > Key Then
j ＝ m － 1
Else
i ＝ m ＋ 1
End If
Loop
If f ＝ True Then
　 Text1.Text＝“數據位置：” ＋ Str(p)
Else
　Text1.Text＝“沒有找到該數據！”
End If
數組元素a(1)到a(9)的值依次為10，15，30，32，38，42，45，48，68，若通過如下程序段查找數據key＝43，則在執行該程序段的過程中，依次訪問的數據是(　　)
A.38，45，42 B.38，45，48
C.38，48，42 D.38，48，45
解析　本題考查的是對分查找的變形。在程序執行過程中，各個變量的值變化情況如下表所示，所以答案選A。

i 1 6 6 7
j 9 9 6 6
m 5 7 6
a(m) 38 45 42
答案　A
3.某對分査找算法的VB程序段如下：
Key ＝ Val(Text1.Text)
i ＝ 1: j ＝ 10：Text2.Text＝“ ”
Do While i <＝ j
m＝(i＋j＋1)\2
If key ＝ a(m) Then Exit Do
If key > a(m) Then j＝m－1 Else i＝m＋1
Text2.Text＝Text2.Text＋Str(a(m))
Loop
已知數組 a(1 To 10)中的數據分別是83、80、66、46、44、36、21、16、15、12，在文本框Text1中輸入80，執行該程序段，文本框Text2中顯示的是(　　)
A.36　66 B.44　88
C.36　46 D.44　66
解析　本題考查的是對分查找的變形。在程序執行過程中，各個變量的值變化情況如下表所示，所以答案是A。

i 1 1 1
j 10 5 2
m 6 3 2
a(m) 36 66 80
答案　A
4.某對分查找算法的VB程序段如下：
Key ＝ Val(Text1.Text) Mod 10
Text2.Text ＝ “ ”
i ＝ 1: j ＝ 10: f ＝ False
Do While i <＝ j And Not f
m ＝ (i ＋ j) \ 2
If a(m) \ 10 ＝ Key Then
　 search ＝ m：f ＝ True
ElseIf a(m) \ 10 < Key Then
　 i ＝ m ＋ 1
Else
　 j ＝ m － 1
End If
Text2.Text ＝ Str(m) ＋ Text2.Text
Loop
數組元素a(1)到a(10)的值依次為：8，15，19，23，35，37，42，48，55，68，文本框Text1中輸入21，執行該程序段，文本框Text2中顯示的是(　　)
A.5　2 B.2　5
C.15　35 D.35　15
解析　本題考查的是對分查找的變形。Key＝1，在程序執行過程中，各個變量的值變化情況如下表所示，所以答案是B。

i 1 1
j 10 4
m 5 2
a(m) 35 15
a(m)\10 3 1
答案　B
能力提升
5.已知一無序數組a(下標1到n)，通過引入數組b(下標1到n)，使得a(b(1))≤a(b(2)) ≤a(b(3))……≤a(b(n))(示例如圖所示)，對這些有序數據可進行對分查找。則第一次查找時，中點位置m與中點值分別是(　　)

A.m的值是Fix((1＋n)/2)，中點值是 a(m)
B.m的值是Fix((1＋n)/2)，中點值是 a(b(m))
C.m的值是Fix((b(1))＋b(n))/2)，中點值是 a(m)
D.m的值是Fix((b(1))＋b(n))/2)，中點值是 a(b(m))
解析　對分查找的數組必須有序，數組a(i)是無序的無法對分查找，但a(b(i))是有序的可以對分查找。第一次查找時，有序數組a(b(i))的中點數據為a(b(3))，也就是m＝3。所以答案是B。
答案　B
6.有如下VB程序段：
Key ＝ Val(Text1. Text)
i ＝ 1: j ＝ 10
flag ＝ False
s ＝“ ”
Do While i <＝ j And Not flag
mid1 ＝ Int(i ＋ (j － i) / 3)
mid2 ＝ Int(j － (j － i) / 3)
If Key ＝ a (mid1) Then
　 flag ＝ True
ElseIf Key 　 j ＝ mid1 － 1
ElseIf Key ＝ a(mid2) Then
　 flag ＝ True
ElseIf Key >a(mid2) Then
　 i ＝ mid2 ＋ 1
Else
　 i ＝ mid1 ＋ 1 ：j ＝ mid2 － 1
End If
s ＝ s & “ ” & mid1 & “：” & mid2
Loop
Text2.Text ＝ s
已知數組 a(1 To 10)中的數據分別是 12、21、34、45、59、63、72、86、94、100，在文本框Text1中輸入34，程序運行后文本框Text2 中顯示的內容是(　　)
A.4：7　1：2 B.4：7　1：2　3：3
C.4：7　1：3　3：3 D.4：7　3：3
解析　本題考查的是對分查找的變形。在程序執行過程中，各個變量的值變化情況如下表所示，所以答案選B。

i 1 1 3
j 10 3 3
mid1 4 1 3
mid2 7 2 3
a(mid1) 45 12 34
a(mid2) 72 21 34
答案　B
7.利用對分査找算法計算整數勾股數對的VB程序段如下：
flag ＝ True : p ＝ 0
Key ＝ 5
For i ＝ 1 To Key － 1
　L ＝ i ＋ 1: R ＝ Key － 1
　Do While L <＝ R And flag
M ＝ (L ＋ R) \'2
p ＝ p ＋ 1
If i * i ＋ M * M < Key * Key Then
　 L ＝ M ＋ 1
ElseIf i * i ＋ M * M > Key * Key Then
　 R ＝ M － 1
Else
　 Text2.Text ＝ Str(i) ＋ “ ”＋Str(M) ＋ “ ” ＋ Str(key)
　 flag ＝ False
　 i ＝ Key
End If
　Loop
Next i
If flag Then Text2.Text ＝ “沒有符合條件的整數勾股數對！”
程序運行后，變量p的值為(　　)
A.3 B.4
C.5 D.6
解析　采用分類討論的方法。當i＝1時，m＝3、4循環2次，i＝2時，m＝3、4循環2次，i＝3時，m＝4循環1次，找到Key為5，符合條件，共循環5次。
答案　C
8.數組元素a(0)到a(9)的值依次為“13，20，22，25，30，33，40，52，65，100”，文本框Text1中輸入的值是33，執行該程序段，下列描述正確的是(　　)
key ＝ Val(Text1.Text)
i ＝ 0: j ＝ 9：　s ＝ 0
Do While i <＝ j
　m ＝ Fix((i ＋ j) \ 2 ＋ 0.5)
　s ＝ s ＋ 1
　If key ＝ a(m) Then
Label1.Caption ＝ Label1.Caption ＋ “→” ＋ Str(m)
Exit Do　′Exit Do表示退出循環
　End If
　If key < a(m) Then j ＝ m － 1 Else i ＝ m ＋ 1
　Label1.Caption ＝ Label1.Caption ＋ “→” ＋ Str(m)
Loop
Label2.Caption ＝ “歷經” ＋ CStr(s) ＋ “步”
A.標簽Label1顯示內容為“→4→7→5”
B.標簽Label2顯示內容為“歷經1步”
C.該程序為順序查找，查找次數為3
D.該程序為對分查找，查找次數為4
解析　本題考查的是對分查找的變形。在程序執行過程中，各個變量的值變化情況如下表所示，標簽Label1顯示內容為“→4→7→5”，標簽Label2顯示內容為“歷經3步”，該程序為對分查找，查找次數為3，故答案是A。

i 0 5 5
j 9 9 6
m 4 7 5
a(m) 30 52 33
答案　A
9.小王編寫了一個實現文字查找替換功能的VB程序，運行界面如圖所示。文本框Text1顯示原文內容，Text2中輸入查找內容，Text3中輸入替換內容，單擊“全部替換”按鈕Command1后，Text4顯示查找替換的結果，Text5中顯示替換的次數，Text6顯示“查找內容”在原文中的起始位置。

實現上述功能的VB程序如下，但加框處代碼有錯，請改正。
Private Sub Command1_Click()
　Dim s As String, result As String, pos As String
　Dim count As Integer, i As Integer
　i ＝ 1: count ＝ 0
　result ＝ “ ”： pos ＝ “ ”
　Do While i <＝ Len(Text1.Text)
s ＝ Mid(Text1.Text, i, Len(Text2.Text))
If s ＝ Text2.Text Then
　 result ＝ result ＋ Text3.Text
　 count ＝ count ＋ 1
　 pos ＝ 　　　′①
　 i ＝ i ＋ Len(Text2.Text)
Else
　　　′②
　 i ＝ i ＋ 1
End If
　Loop
　Text4.Text ＝ result
　Text5.Text ＝ Str(count)
　Text6.Text ＝ pos
End Sub
程序中加框①處應改正為____________________________________________；
加框②處應改正為________________________________________________。
解析　①變量result存儲替換后的新字符串，count存儲替換次數，pos存儲替換位置。程序通過變量i來讀取原字符串中的字符，因此當前的位置是i。
②Else語句對應的情況是：原字符串中取出來的子串不等于替換內容，因此不需要替換，保持原樣，從該行代碼緊接著“i＝i＋1”可得出字符串往后移動一位，因此result需要保存原字符串當前位置i上的一個字符。
答案　①pos＋Str(i)　②result＝result＋Mid(Text1.Text，i，1)
10.某校季運動會共n名運動員參賽，小明編寫了根據號碼牌查詢學生信息的軟件，輸入號碼牌就能查詢該號碼牌所屬的班級和選手姓名。數組a、b、c分別保存了本次運動會所有選手的號碼牌、班級、姓名的信息。第i個選手的號碼牌保存在a(i)中，對應的班級和姓名保存在b(i)和c(i)中。程序界面如圖所示，在文本框Text1中輸入號碼牌，單擊“查詢”按鈕(Command1)，如果找到對應的信息，就顯示所屬班級和選手姓名，如果沒有找到，則顯示“未找到”。

(1)分析程序，可知數據庫的文件名為__________，當前數據表的名稱為：________。
(2)填入適當的語句和代碼，把程序補充完整。
Dim n As Integer　′用于存儲運動員總人數
Dim a(1000) As Integer, b(1000) As String，c(1000) As String
Private Sub Form_Load()
Dim conn As New ADODB.Connection
Dim rs As New ADODB.Recordset
conn.ConnectionString ＝ “Provider ＝ Microsoft.Jet.OLEDB.4.0；DATA Source＝” & App.Path & “\sport.accdb”
conn.Open
Set rs.ActiveConnection ＝ conn
rs.Open “號碼牌”
n ＝ 0
Do While Not rs.EOF　′到記錄集rs的最后一條記錄后退出循環
n ＝ n ＋ 1
　　　　a(n) ＝ rs.Fields(“號碼”)　′讀取當前記錄“號碼”字段值
b(n) ＝ ____①____　′讀取當前記錄“班級”字段值
c(n) ＝ rs.Fields(“姓名”) ′讀取當前記錄“姓名”字段值
　　 ____②____　′移動到下一條記錄
Loop
′按號碼牌升序排序后，顯示在列表框List1中
′其他代碼略。
End Sub
Private Sub Command1_Click()　　
　Dim x As Integer
　x ＝ Val(Text1.Text)
　pos ＝ ______③______
　If pos > 0 Then
Text2.Text ＝ b(pos)：Text3.Text ＝ c(pos)
　Else
Text2.Text ＝ “未找到”
　End If
End Sub
Function Search(Key As Integer) As Integer
　Dim i As Integer, j As Integer，
　i ＝ 1：j ＝ n：Search ＝ 0
　Do While i <＝ j
m ＝ Fix((i ＋ j) / 2)
If Key ＝ a(m) Then
　 Search ＝ m : Exit Function
ElseIf______④______ Then
j ＝ m － 1
Else
i ＝ m ＋ 1
End If
　Loop
End Function
解析　(1)①根據數據文件名的擴展名accdb，在數據庫連接代碼中查找，即可找到sport.accdb。②代碼rs.Open “號碼牌”得知打開的是“號碼牌”數據表。(2)①讀取當前記錄“班級”字段值到數組b中，即b(n)＝rs.Fields(“班級”)。②移動到下一條記錄rs.MoveNext。③調用自定義函數，注意函數參數，將過程中x值傳遞給自定義函數中的key，即：Search(x)。函數的計算結果為數組中對應元素的下標，如果函數結果為0，意味著沒有找到。 ④理解對分查找算法。
答案　(1)①sport.accdb　②號碼牌　(2)①rs.Fields(“班級”)　②rs.MoveNext　③Search(x) ④key < a(m)


(共31張PPT)
第4節　查找算法
考試內容 考試要求
順序查找算法思想及程序實現 c
對分查找算法思想及其變形的程序實現 c
一、順序查找算法思想和程序實現
順序查找的基本思想是從第一個數據開始，按順序逐個將數據與給定的數據(查找鍵)進行比較，若某個數據和查找鍵相等，則查找成功，輸出所查數據的位置；反之，輸出未找到。
For i ＝ 1 To n
If a(i)＝key Then
　Exit For
End If
Next i 代碼分析：將數組中的每個元素逐個與key進行比較，如果相等則查找成功，循環結束。如果循環結束后，變量i的值等于n＋1，則意味著沒有找到。順序查找數組可以無序
二、對分查找算法思想
對分查找又稱二分查找，是一種高效的查找方法。對分查找的前提是被查找的數據是有序的(升序或降序)。對分查找的基本思想是在有序的數列中，首先將要查找的數據與有序數列內處于中間位置的數據進行比較，如果兩者相等，則查找成功；否則就根據數據的有序性，再確定該數據的范圍應該在數列的前半部分還是后半部分；在新確定的縮小范圍內，繼續按上述方法進行查找，直到找到要查找的數據，即查找成功，如果要查找的數據不存在，即查找不成功。
若key為查找關鍵字，數組d存放n個已按升序排序的數據。使用對分查找時，把查找范圍[i，j]的中間位置上的數據d(m)與key進行比較，結果必然是如下三種情況之一：
(1)若key(2)key＝d(m)，找到了需要的數據；
(3)key>d(m)，查找鍵大于中點d(m)處的數據。由數組d中的數據的遞減性，可以確定：在(i, m)內不可能存在值為key的數據，必須在新的范圍(m＋1，j)中繼續查找。
這樣，除了出現情況(2)，在通過一次比較后，新的查找范圍將不超過上次查找范圍的一半。
數組d為例，觀察對分查找的過程。要查找的數據key＝52，查找過程如下：
三、對分查找算法代碼實現
i ＝ 1: j ＝ n: s ＝ 0
Do While i <＝ j
　 m ＝ (i ＋ j) \ 2
　 If a(m) ＝ key Then
　s ＝ m: Exit Do
　 ElseIf key < a(m) Then
　j ＝ m － 1
　 Else
　i ＝ m ＋ 1
　 End If
Loop 左邊程序實現在升序數組a(1)…a(n)中查找值等于key的元素，將其下標存儲在s中。如果沒有找到則s值為0，如果找到，則s存儲對應元素的下標。
對分查找前提是數據有序，對n個數據查找，最多查找次數為Log2n＋1(向下取整)。
例如在有序數組a(1)…a(10000)中查找某個值，最多需要查找Log210000＋1，即14次
一、順序查找算法思想和代碼實現
【典例1】 小王拿著一大串鑰匙去開倉庫的某一扇門，由于鑰匙上沒有任何標記，小王只能將這一串鑰匙一把一把地去試，從算法角度看，小王的做法屬于(　　)
A.冒泡排序 B.選擇排序
C.對分查找 D.順序查找
解析　本題考查兩個算法的區別。順序查找的思想第從第一個數據開始，按數據的順序逐個將數據與給定的值進行比較，若某個數據與給定的值相等，則查找成功，否則查找不成功。
答案　D
【變式訓練】 用對分查找法和順序查找法在數字序列“1，2，3，5，8，13，21，34，55”中查找數字13，兩種方法都能訪問到的數字是(　　)
A.3 B.5
C.8 D.34
解析　對分查找訪問到的數字為8、21、13，順序查找訪問到的數字為1，2，3，5，8，13。兩者共同為8。
答案　C
二、對分查找算法思想
【典例2】 已知單調函數f(x)在[0，1]區間存在一個x0，使f(x0)＝0。現用對分查找法搜索x0的值，開始搜索區間為[0，1]，若經過10次對分查找后還需繼續搜索，則第11次搜索區間的長度為(　　)
A.1/2 B.1/10
C.1/102 D.1/210
解析　對分查找的每次區間變為上次的二分之一。第2次為原搜索區間的長度1/2，第3次為原搜索區間的長度1/4……第11次為原搜索區間的長度1/210，所以答案D。
答案　D
【變式訓練】 下列有關查找的說法，正確的是(　　)
A.進行對分查找時，被查找的數據必須已按升序排列
B.進行對分查找時，如果查找的數據不存在，則無需輸出結果
C.在新華字典中查找某個漢字，最適合使用順序查找
答案　D
【典例3】 數組變量d(1)到d(8)的值依次為97、86、79、68、56、41、33、13，用“對分查找”找到“13”的過程中，依次被訪問到的數據是(　　)
A.68、13 B.68、41、13
C.56、41、33、13 D.68、41、33、13
解析　本題考查標準的對分查找，查找中間項為m＝(i＋j)\2，經過4次對分查找。
答案　D
i 1 5 7 8
j 8 8 8 8
m 4 6 7 8
d(m) 68 41 33 13
【變式訓練】 在有序單詞序列“bike，cake，data，easy，feel，great，hive，mark，sweet”中，用對分查找算法找到“easy”過程中，依次被訪問到的數據為(　　)
A.feel, data, easy B.great, data, easy
C.bike, cake, dada，easy D.feel，cake，data，easy
解析　本題考查標準的對分查找，查找中間項為m＝(i＋j)\2，經過4次對分查找。
i 1 1 3 4
j 9 4 4 4
m 5 2 3 4
d(m) feel cake data Easy
答案　D
三、對分查找算法代碼實現
【典例4】 某對分査找算法的VB程序段如下：
i ＝ 1: j ＝ 9: n ＝ 0
key ＝ Val(Text1.Text)
Do While i <＝ j
　n ＝ n ＋ 1
　m ＝ Fix((i ＋ j) / 2)
　If key ＝ d(m) Then Exit Do　′Exit Do表示退出循環
　If key < d(m) Then j ＝ m － 1 Else i ＝ m ＋ 1
Loop
數組元素d(1)到d(9)的值依次為“7，12，18，25，39，58，61，72，86”。若該程序段運行結束后，n的值為2，則key的值是(　　)
A.39 B.18或61
C.18或72 D.12或61
解析　n代表查找次數，代入選項計算查找次數為2，即為答案。key＝12，第1次：m＝5，i＝1，j＝4；第2次：m＝2 ，d(m)＝12查找成功。key＝61，第1次：m＝5，i＝6，j＝9；第2次：m＝7 ，d(m)＝61查找成功。所以答案選D。
答案　D
【變式訓練】 采用如下對分查找算法對數組a中7個有序數據“15，38，51，66，77，81，99”進行查找，查找數據為“55”，
i ＝ 1: j ＝ 7: x ＝ 55
Do While i <＝ j
m ＝ (i ＋ j) \ 2
If a(m) ＝ x Then Exit Do
If a(m) > x Then j ＝ m － 1 Else i ＝ m ＋ 1
Loop
執行完上述代碼后，根據最終變量值判斷下列表達式，其中正確的是(　　)
A.i＝m＋1 B.i＝m－1
C.j>m＋1 D.j解析　本題考查標準的對分查找，查找中間項為m＝(i＋j)\2，最終沒有找到該數據。算法結束時i＝4，j＝3，m＝3，所以答案選A。
答案　A
i 1 1 3 4
j 7 3 3 3
m 4 2 3 ?
d(m) 66 38 51 ?
【典例5】 有如下VB程序段：
i ＝ 1 : j ＝ 10 : flag ＝ True : n ＝ 0
Key ＝ Val(Text1.Text)
Do While i <＝ j And flag ＝ True
m ＝ (i ＋ j) \ 2
If a(m) ＝ Key Then
flag ＝ False
ElseIf a(m) > Key Then
i ＝ m ＋ 1 : n ＝ n － 1
Else
j ＝ m － 1 : n ＝ n ＋ 1
End If
Loop
數組元素a(1)到a(10)依次是99, 94, 90, 87, 70，69，60，56，45，36，變量n的值最終是0，則文本框Text1輸入的數字可能是(　　)
A.100 B.87 C.69 D.41
解析　本題考查的是對分查找的變形。當key＝100時，程序執行過程中，各個變量的值變化情況如下表所示：
i 1 1 1 1
j 10 4 1 0
m 5 2 1 ?
d(m) 70 94 99 ?
n 1 2 3 ?
當key＝87時，程序執行過程中，各個變量的值變化情況如下表所示：
i 1 1 3 4
j 10 4 4 4
m 5 2 3 4
d(m) 70 94 90 87
n 1 0 －1 ?
當key＝69時，程序執行過程中，各個變量的值變化情況如下表所示：
i 1 6 6
j 10 10 7
m 5 8 6
d(m) 70 56 69
n －1 0 ?
當key＝41時，程序執行過程中，各個變量的值變化情況如表所示。
i 1 6 9 10 10
j 10 10 10 10 9
m 5 8 9 10 ?
d(m) 70 56 45 36 ?
n －1 －2 －3 －2 ?
答案　C
【變式訓練】 有如下VB程序段：
i ＝ 1: j ＝ 9: f ＝ False
Do While i <＝ j And Not f
m ＝ Fix((i ＋ j) / 2)
If a(m) ＝ Key Then
p ＝ m : f ＝ True
End If
If a(m) > Key Then
j ＝ m － 1
Else
i ＝ m ＋ 1
End If
Loop
If f ＝ True Then
　 Text1.Text＝“數據位置：” ＋ Str(p)
Else
　Text1.Text＝“沒有找到該數據！”
End If
數組元素a(1)到a(9)的值依次為10，15，30，32，38，42，45，48，68，若通過如下程序段查找數據key＝43，則在執行該程序段的過程中，依次訪問的數據是(　　)
A.38，45，42 B. 38，45，48 C.38，48，42 D. 38，48，45
解析　本題考查的是對分查找的變形。在程序執行過程中，各個變量的值變化情況如下表所示，所以答案選A。
答案　A
i 1 6 6
j 9 9 6
m 5 7 6
d(m) 38 45 42
【典例6】 小明為了研究對分查找的過程中數據被訪問的情況，編寫了一個VB程序，功能如下：在列表框List1中顯示已經排序的數據(存儲在數組a中)，在文本框Text1中輸入要查找的數據，單擊“查找”按鈕Command1后，在標簽Label1中顯示查找中依次被訪問到的數據。程序運行界面如圖所示。
實現上述功能的VB程序如下，但加框處代碼有錯，請改正。
Const n ＝ 10
Dim a(1 To n) As Integer
Dim s As String
Private Sub Form_Load()
′產生隨機數依次存儲在數組a中，代碼略
′對數組a升序排序并在列表框輸出，代碼略
End Sub
Private Sub Command1_Click()
　Dim x As Integer, p As Integer
　x ＝ Val(Text1.Text)
　s ＝ “ ”
　If p > 0 Then s ＝ s ＋ “查找成功” Else s ＝ s ＋ “查找失敗”
　Label1.Caption ＝ “依次被訪問的數據為：” ＋ s
End Sub
Function search(key As Integer) As Integer
　Dim i As Integer, j As Integer, flag As Boolean
　flag ＝ False
　i ＝ 1: j ＝ n: search ＝ 0
　Do While i <＝ j And Not flag
m ＝ (i ＋ j) \ 2
If a(m) ＝ key Then
　 search ＝ m
　 flag ＝ True
　j ＝ m － 1
Else
　i ＝ m ＋ 1
End If
s ＝ s ＋ Str(a(m)) ＋ “→”
　Loop
End Function
程序中加框(1)處應改正為_________________________________________；
加框(2)處應改正為________________________________________________。
解析　(1)聯系下文代碼If p > 0 Then，需要對變量p賦值，結合函數search的功能：如果在數組a中找到要查找的數，函數search 返回該數在數組中的位置，如果沒有找到，函數search 返回值為0，結合程序得知第1空為：p＝search(x)。
(2)在一個塊If語句中結合對分查找算法得出第2空為： ElseIf Key < a(m) Then。
答案　(1)p＝search(x)　(2)ElseIf Key < a(m) Then

展開更多......

收起↑