資源簡介

(共75張PPT)
課時5　二分查找
第五章　數據結構與算法
1.通過實例分析，理解順序查找的基本思想，掌握使用二分查找的一般方法。
2.能根據不同的應用場景，選擇合適的數據結構，能靈活使用二分查找算法編寫程序。
目 錄
CONTENTS
知識梳理
01
例題精析
02
隨堂檢測
03
鞏固與提升
04
知識梳理
1
1.二分查找(Binary Search)
二分查找又稱對分查找或折半查找。
二分查找是指在有序的數據序列中，首先將要查找的數據元素與數組的____________元素進行比較，如果相等，則查找成功并退出查找；否則，根據數組元素的有序性，確定新的____________(在數組的前半部分還是在后半部分)；在確定了新的查找范圍后，重復進行以上操作，直到找到或查找結束為止。
①二分查找的前提條件是待查找的數據序列必須有序。
②“未找到”是指當前查找區間不存在，即區間左端點大于右端點。
中間位置
查找范圍
2.二分查找的算法框架
說明：要查找的目標數據元素為key，待查找的數據元素存放在數組d中。
i、j分別為查找區間的起點位置和終點位置，m為查找區間的中間位置，n為數據元素個數。
i＝0
j＝n－1
while i<＝j：
#計算中點位置m
#比較key與d[m]，并做相應處理
#若i>j，則表示未找到
3.二分查找的程序實現
·設要查找的數據是key，待查找的數據元素存放在數組d中，并已按升序排序。
·輸出查找結果，若找到則輸出信息“找到！位置為：X”，否則輸出“查無此數！”
·輸出查找次數c。
二分查找主要代碼如下(以升序為例)：
輸入key的值
c＝0　　　　　　　#記錄查找次數
find＝False　　　　#設置find的初值
i＝0　　　　　　　#區間左端點位置
j＝n－1　　　　　 #區間右端點位置
while _____________________：　#還未找完并且還未找到，則繼續查找
c＝c＋1　　　　#查找次數記數
m＝____________　 #計算中點位置m，等價于m＝int((i＋j)/2)
if key＝＝d[m]：　 #找到目標元素，并進行相應處理
find＝True
print(m)
if key>d[m]：　　#表示要查找的元素比中間位置上的元素大時
i＝m＋1　　　#調整區間左端點
i<＝j and not find
(i＋j)∥2
else：　　　　　
j＝m－1　　　#調整區間右端點
if find＝＝False：
print(″查無此數！″)
print(″查找次數為：″，c)
例題精析
2
例1 有如下兩組數據：
A
①1，2，3，4，5，6，7，8，9
②3，4，5，2，1，8，7，6，9
A.①②都可以直接使用二分查找
B.①②都可以直接使用順序查找
C.①可以直接使用順序查找，也可以直接使用二分查找
D.②可以直接使用順序查找，但不能直接使用二分查找
解析　本題主要考查的是使用順序查找和對分查找的適用條件。順序查找對待查找的數據沒有要求，而二分查找的前提是數據必須有序。①中數據有序，②中數據無序，①中數據順序查找和二分查找均可以直接使用，②中數據只能使用順序查找，若要使用二分查找，則先對②中數據進行排序操作。因此，不正確的是A，答案為A。
變式訓練　分別使用順序查找算法和二分查找算法在數據序列“5，6，10，13，15，20，21，26，30”中查找數據10，下列關于查找的次數的說法中正確的是(　　)
A.順序查找2次，二分查找3次 B.順序查找3次，二分查找2次
C.順序查找3次，二分查找3次 D.順序查找3次，二分查找4次
解析　本題主要考查的是順序查找和二分查找的算法思想。數據10是數據序列中第3個元素，因此使用順序查找時，共查找次數為3次，使用二分查找時，依次被訪問的數據為15、6、10，即二分查找的次數也為3次。因此，答案為C。
C
例2 在列表lista中存儲的數據依次為：88，78，70，65，60，55，51，45，39，28。現使用二分查找算法在列表lista中查找數據51，共需查找的次數為(　　)
A.1次 B.2次 C.3次 D.4次
解析　本題主要考查的是二分查找的查找過程。第一次找到的索引號為4的數據(60)，因為51<60，因此向右查找，第二次找到索引號為7的數據(45)，因為51>45，因此向左查找，第三次找到索引號為5的數據(55)，因為51<55，因此向右查找，第四次找到索引號為6的數據(51)，找到要找的數據后結束查找，因此共查找了4次，答案為D。
D
變式訓練　有100個英語單詞已按升序排序并存儲在列表listb中，現要使用二分查找算法在列表listb中查找某個單詞，則最多的查找次數為(　　)
A.5次 B.6次 C.7次 D.8次
解析　本題主要考查的是計算二分查找的查找次數。N個數據，使用二分查找，查找次數最多為log2(n)取整加1，現共有100個單詞，因此最多次數為7次，答案為C。
C
例3 某二分查找算法的Python程序段如下：
n＝0; flag＝True
key＝int(input(″輸入要查找的數：″))
i，j＝0，9
while i<＝j and flag：
m＝(i＋j)∥2
if a[m]＝＝key：
flag＝False
elif a[m]i＝m＋1
n＝n＋1
else：
j＝m－1
n－＝1
解析　本題主要考查二分查找算法。用二叉搜索樹畫出各個元素的搜索順序，圖中各個左子樹方向可以讓n自減，右子樹方向可以讓n自增。
B
A選項，若key＝25，則從節點23的右側出循環，此時m、n的值是3、2，同理key＝45, m、n的值是8、2，key＝60，m、n的值是9、2。key＝34，m、n的值是6、1。
變式訓練　某二分查找算法的Python程序段如下：
b＝[98，86，81，77，66，60，48，20]
key＝int(input(″key＝″))
i，j＝0，len(b)－1
s＝″″
while i<＝j：
m＝(i＋j)∥2
if b[m]＝＝key：
s＝s＋″M″
break
if keyi＝m＋1
s＝s＋″R″
else：
j＝m－1
s＝s＋″L″
print(s)
程序執行時，輸入key的值為55，則輸出的結果為(　　)
A.RRL B.RLR C.RRLR D.RRLM
解析　本題主要考查的是二分查找時的方向問題。本題的功能是求使用二分查找在降序序列中查找數據55的過程，如果找到，則記為“M”，如果要查找的數據在序列的右邊區間中，則記為“R”，否則記錄為“L”。因此，答案為A。
A
例4 有如下 Python 程序段：
def search(i，j)：
　while i<＝j：
　 m＝(i＋j)∥2
　 if a[m]>a[m－1] and a[m]　　　 i＝m＋1
　elif a[m]a[m＋1]:
　　　j＝m－1
　 else：
return m
a＝[3，11，20，25，30，36，50，49，37，16]
print(a[search(0，9)])
程序執行后輸出的結果為(　　)
A.50 B.6 C.7 D.49
解析　本題考查二分查找以及其變式。a[m－1]，a[m]，a[m＋1]如果是連續上升的序列，往后找 i＝m＋1 a[m－1]，a[m]，a[m＋1]如果是連續下降的序列，往前找 j＝m－1，a[m－1]，a[m]，a[m＋1]如果不滿足連續上升或者下降，則直接輸出m。
A
變式訓練　有如下 Python 程序段：
import random
a＝['A'，'#'，'B'，'C'，'D'，'E'，'#'，'F']
i＝0
j＝len(a)－1
x＝random.choice('ABCDEF') #從字符串'ABCDEF'中隨機選出一個字符
while i<＝j：
　　mid＝(i＋j) ∥ 2
　　if a[mid]＝＝x:
　break
　　elif a[mid]＝＝ '#' or a[mid]>x:
　j＝mid－1
　　else：
　i＝mid＋1
print(a[mid])
A.A B.B C.C D.D
解析　本題考查二分查找的算法思想。根據題目要求，畫出相應的二叉樹，當找到#號時，向左查找，因此不可能找到B。
B
隨堂檢測
3
A.使用順序查找算法查找數據10，共查找了3次
B.使用二分查找算法查找數據10，共查找了3次
C.使用順序查找算法查找數據25，共查找了7次
D.使用二分查找算法查找數據25，共查找了3次
D
解析　本題主要考查的是順序查找和二分查找算法思想。使用二分查找算法查找數據25，需要的查找次數為4次，因此D選項不正確，答案為D。
2.在7個有序的數列“a1，a2，a3，a4，a5，a6，a7”中，采用二分查找法查找數值key，依次需要進行比較的數據可能是(　　)
A.a4 B.a4，a6，a2
C.a4，a2，a5 D.a4，a6，a5，a7
A
解析　本題考查二分查找的算法思想。第1次查找的是最中間的節點a4，因此A選項正確。B選項a2比a4小，查找到a6后，不可再去找a2。C選項a5比a4大，也不可能。D選項第3次查找，要么a5或a7，不可能2個數同時被查找到。
3.某對分查找算法的Python程序段如下：
a＝[85，74，70，65，54，36，30，28，26，12]
t＝″″
i，j＝0，9
key＝30
f＝False
while i<＝j and not f：
m＝(i＋j)∥2
t＋＝str(m)
if a[m]＝＝key：
f＝True
elif a[m]>key：
i＝m＋1
t＝t＋″→″
else：
j＝m－1
t＝t＋″←″
C
執行該程序段，變量t的值是(　　)
A.″4→7←5→″ B.″4→7←5→6→″
C.″4→7←5→6″ D.″4→7→5→6→″
解析　本題主要考查的是二分查找的程序實現。本題的功能是在一個降序數列中查找key的過程，記錄每次訪問的元素，并標識查找的方向(向右→或向左←)。在數列中查找30的過程中，第一次查找時，m＝4，t＝“4”，因為a[4]＝54>key，因此向右查找，i＝5，t＝“4→”；第二次查找時，m＝7，t＝“4→7”， 因為a[7]＝28key，因此向右查找，i＝6，t＝“4→7←5→”；第四次查找時，m＝6，t＝“4→7←5→6”， 因為a[6]＝＝key，因此查找結束，故答案為C。
4.某二分查找算法的Python程序段如下：
a＝[125，117，115，108，102，95，88，63，51，36]
key＝108
i，j＝0，len(a)－1
ss＝″″
while i<＝j：
m＝int((i＋j)/2＋0.5)
ss＝ss＋str(m)
if key＝＝a[m]：
break
if keyC
i＝m＋1
ss＝ss＋″>>″
else：
j＝m－1
ss＝ss＋″<<″
print(ss)
執行該程序段，輸出的內容為(　　)
A.4<<1>>2>>3 　 B.5<<2<<4>>3
C.5<<2>>4<<3 D.5<<2>>4>>3
解析　本題主要考查的是二分查找的變式。本題中將中間位置m的計算公式修改為m＝int((i＋j)/2＋0.5)，即在偶數個數的區間中，找到的m為中間靠右的位置，因此，在查找數據108的過程中，依次訪問的元素位置為5、2、4、3，注意左右方向的表示。查找結束時，字符串ss的內容為5<<2>>4<<3，答案為C。
5.某對分查找算法的Python程序段如下：
n＝len(a)
f＝[0]*n
key＝int(input(″輸入要查找的數：″))
i，j＝0，n－1
while i<＝j：
m＝(i＋j)∥2
f[m]＝1
if a[m]>＝key：
j＝m－1
else：
i＝m＋1
D
A.5 B.8 C.14 D.15
解析　本題考查對分查找的次數。本題為對分查找，數組f標記查找過的下標，若為3，表明共查找了3次。而該題中，查找找到不退出，退出的唯一條件是j。我們可以根據選項n的數量畫出二叉判定樹，若不存在從第三層結束的可能，就是不可能選項。
6.有如下Python程序段：
key＝int(input())
i＝0；j＝len(a)－1
s＝″″
while i<＝j：
　　m＝(i＋j＋1)∥2
　　if key＝＝a[m]：
break
　　if keyj＝m－1
　　else：
i＝m＋1
　　s＋＝str(a[m])＋″，″
print(s[：－1])
B
若數組元素a的值為[6，15，18，20，25，30，35，38，41，46]，輸入正整數key值，執行該程序段，輸出的值可能是(　　)
A.30，20 B.30，41，38
C.25，15，6 D.25，38，41
解析　根據二分查找算法畫出對應的二叉樹為 ，
可以得到遍歷的路徑。
7.有如下 Python 程序：
import random
a＝[15，18，25，34，38，40，55，61，80，85]
key＝random.randint(15，55)
f＝[0]*10
i＝0；j＝len(a)－1
while i<＝j：
　　m＝(i＋j＋1)∥2
　　if a[m]>key：
　j＝m－1
　else：
　if a[m]%5＝＝0：
　　　f[m]＝1
　i＝m＋1
D
執行該程序段后，列表 f 值可能是(　　)
A.[0，0，1，0，0，1，0，0，0，0]
B.[0，0，0，0，0，1，0，0，1，0]
C.[1，0，1，0，0，0，0，0，0，0]
D.[0，0，0，0，0，1，1，0，0，0]
解析　考查二分查找算法的算法思想。f[m]賦值語句的執行條件 a[m]<＝key and a[m]%5＝＝0，即向右查找過程中，節點是5的倍數。產生數的范圍是[15，55]，那么只可能查找[40，55]之間的數，第1次向右查找的節點為40，第2次查找的節點是55，即只能查找55。
8.有如下 Python 程序段：
def binSearch(i，j，key)：
　if i>j：
　return－1
　m＝(i＋j)∥2
　if key＝＝a[m]：
　 return m
　if key　return binSearch(i，m－1，key)＋m
　return binSearch(m＋1，j，key)＋m
n＝7
a＝[5，6，7，8，9，9，11]
key＝int(input(″輸入查找鍵：″))
print(binSearch(0，n－1，key))
B
解析　本題考查遞歸法求二分查找，找到后返回中間位置，沒有找到，累加找過的位置m。用索引位置畫出二叉樹為 ，沒有一條分支節點和為8。
4
鞏固與提升
基礎鞏固
能力提升
A.使用對分查找查找數據60，共查找了3次
B.使用順序查找查找數據60，共查找了1次
C.使用對分查找查找數據35，共查找了3次
D.使用順序查找查找數據35，共查找了8次
C
解析　本題主要考查的是順序查找和二分查找算法思想。使用二分查找算法查找數據35，需要的查找次數為4次，因此C選項不正確，答案為C。
2.列表數組a中存儲了6個元素，依次為105、110、112、118、120、126，若采用二分查找算法在該列表中查找數據126，則在查找126的過程中依次被訪問到的元素為(　　)
A.118、126 B.118、120、126
C.112、120、126 D.112、120、118、126
C
解析　本題主要考查的是二分查找的算法思想。使用二分查找算法查找數據126的過程中，首先被訪問到的元素為112，第二次被訪問到的元素為120，第三次被訪問到的元素為126，因此，答案為C。
3.某二分查找算法的Python程序段如下：
list1＝[2，6，8，9，12，15，18，20]
key＝int(input(″請輸入待查找的數據：″))
s＝″″
c，i，j＝0，0，7
while i<＝j：
c＋＝1
m＝(i＋j)∥2
if list1[m]＝＝key：
　　s＝s＋str(m)
break
if list1[m]>key：
j＝m－1
else：
i＝m＋1
s＝s＋str(m)＋″→″
print(s)
D
執行該程序段，輸入待查找的數key為12，則輸出的結果是(　　)
A.4→5→ B.4→6→5 C.3→5→4→ D.3→5→4
解析　本題主要考查的是二分查找的程序實現。使用二分查找算法查找數據12的過程中，第一次訪問的是索引號為3的元素9，第二次訪問的是索引號為5的元素15，第三次訪問的是索引號為4的元素12，查找結束，因此，答案為D。
4.某二分查找算法的Python程序段如下：
list1＝['Carrot'，'Celery'，'Garlic'，'Lettuce', 'Mooli', 'Onion'，'Potato'，'Tomato']
key＝list1[2]
left，right＝0，len(list1)－1
c＝0
while left<＝right：
m＝(left＋right)∥2
c＝c＋1
if list1[m]>key：
right＝m－1
else：
left＝m＋1
print(list1[left])
B
程序執行后，下列說法正確的是(　　)
A.變量c的值為4
B.程序輸出的結果為Lettuce
C.變量left的值為2
D.變量right的值為3
解析　本題主要考查的是二分查找的變式。本題的功能是在列表list1中查找第1個大于key的元素。c表示共查找的次數，共查找了3次，因此A選項錯誤；查找結束時，left＝3，right＝2，因此CD選項錯誤；查找結束時，因為left＝3，因此程序輸出的結果為Lettuce，答案為B。
5.某二分查找算法的Python程序段如下：
key＝int(input(″請輸入查找鍵：″))
i＝0
j＝8
f＝[0]*9
while i<＝j：
m＝(i＋j)∥2
f[m]＝1
if a[m]＝＝key：
break
if a[m]>key：
j＝m－1
else
i＝m＋1
C
A.1，1，0，0，1，0，0，0，0 B.0，0，0，0，1，0，0，0，0
C.0，0，0，0，1，1，1，1，0 D.0，1，1，1，1，0，0，0，0
解析　本題主要考查的是二分查找的過程。數組f中元素為1，表示查找過數組a對應位置上元素，f中元素為0，表示數組a對應位置上元素沒有查找過；選項C查找的路徑不符合二分查找算法的過程，答案為C。
6.有如下對分查找程序，A為按非降序排序的整型數組。
import random
key＝random.randint(0，4)*2＋20
a＝[12，14，15，15，19，x，20，24，y，26]
c＝0；n＝10；ans＝0
i＝0；j＝n－1
while i<＝j：
m＝(i＋j)∥2
if a[m]<＝key ：
i＝m＋1
else：
j＝m－1
c＋＝1
D
測試所有可能的key值，程序執行后c均等于4，下列正確的x，y值可以為(　　)
A.19，25 B.20，26 C.20，25 D.20，24
解析　由C始終等于4得，查找次數必定為4次，該對分查找并沒有找到即break結束循環的語句，所以可以把該對分查找程序看作不斷排除的過程，即i＞j表示排除完所有的數據節點，則程序結束，即對應的二叉排序樹根據條件遍歷到葉子節點為止。根據隨機函數產生的key最小為20，若x為19，key＝20，則C等于3，排除A；若y是26，key＝24，則C為3，排除B；若y是25，key＝24，則C為3，排除C。
7.有如下Python程序：
import random
nums＝[11，23，35，44，57，68，76，89]
target＝random.randint(20，70) #隨機生成[20，70]區間內的一個正整數
lst＝[]
left，right＝0，len(nums)－1
while left<＝right：
　　lst.append([left，right]) #為 lst追加一個元素
　　mid＝(left＋right)∥2
　　if nums[mid]＝＝target:
break
　　elif nums[mid]　left＝mid＋1
　　elif nums[mid]>target:
　right＝mid－1
D
A.1 B.2 C.3 D.4
解析　本題考查二分查找。列表長度就是二分查找的查找次數。列表共 8 個元素，最少 1 次，最多 4 次。查找到 76 時，不可能繼續往右查找，所以 4 次是不可能的。
8.有如下Python 代碼：
n＝int(input(″請輸入一個數：″))
a＝[i for i in range(n)]
c＝0
for i in range(1，n)：
　L＝1；R＝i－1
　while L<＝R：
　 m＝(L＋R)∥2
　if a[i]*a[m]＝＝n：
　　　c＋＝1
　　　break
　 elif a[i]*a[m]　　　L＝m＋1
　else：
　　　R＝m－1
print(c)
C
輸入36，執行程序后，輸出結果是(　　)
A.1 B.2 C.3 D.4
解析　本題考查二分查找。程序的功能是數組a的i索引前找一個數，滿足a[i]*a[m]＝＝n的個數，因此分別是9*4、12*3、18*2。
9.某對分查找算法的Python 程序如下：
f＝[0]*20
i＝0；j＝19；n＝0；m＝0
while i<＝j and f[m]＝＝0：
　m＝(i＋j＋1)∥2
　 n＝n＋1
　if a[m]＝＝key：
　f[m]＝1
　elif a[m]　j＝m－1
　else：
　i＝m＋1
D
A.a[1] B.a[4] C.a[12] D.a[16]
解析　本題考查二分算法以及二分判定樹。根據本題代碼m＝(i＋j＋1)∥2，畫出二分判定樹，位于二分判定樹第4層的節點下標分別是1、4、7、9、12、14、17、19。所以key的值不可能是a[16]。
10.有如下Python程序段：
import random
d＝[28，37，39，42，45，50，70，80]
i，j，n＝0，len(d)－1，0
key＝random.randint(20，35)*2
while i<＝j：
　m＝(i＋j)∥2; n＋＝1
　 if key＝＝d[m]：
　break
　elif key　j＝m－1
　else：
　i＝m＋1
print(i，j，m，n)
B
執行該程序段后，下列說法正確的是(　　)
解析　考查二分查收算法思想。Key是[40，70]區間的偶數，n是循環次數。畫出相應的二叉樹。最多查找3次；a[1]為37，查找的位置不可能是1。若查找2次，說明查找的數是50，中間退出循環，滿足條件i<＝j。
A.n的值可能為4
B.若n值為2，則必定滿足i<＝j
C.m的值可能為1
D.若n值為3，則key的值可能是45
11.有如 Python 程序段：
import random
def find(x，y)：
　m＝(x＋y＋1)∥2
　　if a[m]＝＝key：
　return m
　if a[m]>key：
　y＝m－1
　else：
　x＝m＋1　
return find (x，y)
a＝[2，4，6，8，10，12，14，16]
key＝random.choice(a) #從序列的元素中隨機挑選一個元素
i＝0；j＝len(a)－1
xb＝find(i，j)
print(xb，key)
解析　本題考查二分查找、自定義函數的綜合應用。由“key＝random.choice(a)”可知查找鍵 key 是一定可以找得到的，由題中算法可知，找到最少找 1 次，最多找 int(log2n)＋1 次，本題中序列 a 中共有 8 個成員，則最多找 4 次。
上述程序執行完后，函數find被調用的最多次數是(　　)
A.3 B.4 C.5 D.6
B
12.有如下 Python 程序段：
import random
a＝[90，15，40，72，59，32，81，6]
b＝[7，1，5，2，4，3，6，0]
i，j＝0，len(a)－1
key＝random.randint(30，60)
p＝－1
while i<＝j：
　 m＝(i＋j)∥2
　 if a[b[m]]＝＝key:
　p＝b[m]
　break
　 elif a[b[m]]　i＝m＋1
else：
　j＝m－1
print(p)
B
解析　本題考查索引排序和二分查找算法。key 值在 30－60，在列表 a 中只有 40、 59、32 符合范圍，對應的索引值為2，4，5。
13.某二分查找算法的程序段如下：
key＝int(input('待查數據為：'))
i＝0；j＝10；n＝0
while i<＝j:
　 m＝(i＋j＋1)∥2
　if a[m]＝＝key:
break
　elif a[m]>key:
　　　j＝m－1；n＝n－1
　else:
　　　i＝m＋1；n＝n＋1
C
執行該程序段后，下列說法正確的是(　　)
A.該程序若要實現對分查找，要求數組a按降序排列
B.若n為－2，則查找key值可能等于a[3]的值
C.若n為2，則查找 key 的值可能小于a[10]
D.n的值最小為－4，最大為4
解析　本題考查二分查找算法。A選項由條件a[m]>key可以看出數組是升序。B選項查找a[3]需訪問a[5]→a[2]→a[4]→a[3]，則n的值為－1。C選項由訪問路徑 a[5]→a[8]→a[10]→a[9]→end，則n的值為n值為2。D選項如果要n的值最小為－4，最大為4，至少節點數滿15個，本題節點數只有11個。
14.已知一無序數組a，通過引入數組b，使得a[b[0]]≤a[b[1]]≤a[b[2]]……≤a[b[n－1]](示例如下圖所示)，對這些有序數據可進行對分查找。則第一次查找時，中點位置m與中點值分別是(　　)
A.m的值是(n－1)∥2，中點值是a[m]
B.m的值是(n－1)∥2，中點值是a[b[m]]
C.m的值是(b[0]＋b[n－1])∥2，中點值是a[m]
D.m的值是(b[0]＋b[n－1])∥2，中點值是a[b[m]]
B
解析　本題主要考查的是對分查找算法。常見的錯誤思想為：根據a[b[0]]≤a[b[1]]…≤a[b[n－1]]可知數據是有序，因而想當然地認為：m的值為((b[0]＋b[n－1]∥2)，中點值是a[m]。其實，中間數據為a[b[(0＋n－1)∥2]]，例如 a[b[0]]≤a[b[1]]≤a[b[2]]，中點值為a[b[(0＋2)∥2))即a[b[1]]。因此，答案為B。
15.生成并輸出二分查找樹。在有序序列中查找某個數據，常使用二分查找算法。當待尋找的數據為隨機值時，需要使用二分查找樹列舉所有可能情況。所謂二分查找樹，是指按照二分查找的順序，按層次輸出以各中點元素為節點的二叉樹。例如，當遞增數組a＝[1，2，3，4，5，6，7，8，9，10，11，12，13，14，15，16]時，其對應的二分查找樹如圖所示。
下列代碼能夠生成并輸出二分查找樹，請回答下列問題：
(1)當有序數組a＝[2，23，40，45，60，65，68，83，86，95]時，對應的二分查找樹中第3行第3個數為________。
(2)請在劃線處填入合適的代碼。
def create_bs(a)：　#生成并輸出二分查找樹
　　max_cnt＝0
　　n＝len(a)
　　pos＝[0]*n　#pos[i]表示元素a[i]查找的次數
　　for p in range(n)：
　 　　　L，R＝0，n－1
　　 　　cnt＝0
　　　 　while L<＝R：
　　　　 m＝___________
　　　　cnt＋＝1
　　　　if cnt>max_cnt：
　　　　 max_cnt＝cnt
　　　　if m＝＝p：
　　　　　pos[m]＝___________
　　　　　break
　　elif m　　　L＝m＋1
　　else：
　　　　R＝___________
for i in range(1，max_cnt＋1)：
　　s＝″″
　　for j in range(n)：
　　　if pos[j]＝＝i：　#找到節點a[j]
　　　　　　s＝s＋str(a[j])
　　　　else：
　　　　　　　　s＝s＋″　″
　　　　　print(s)
a＝list(range(1，17))
print(″有序數組：″，a)
print(″二分查找樹：″)
create_bs(a)
答案　(1)65　(2)①(L＋R)∥2　②cnt　③m－1
解析　(1)按照題意畫出二分查找樹，可知第3行第3個數為65；(2)中點m表示式左偏，即m＝(L＋R)∥2；程序遍歷數組a，計算當a[p]作為中點元素時，需要查找的次數，存儲到數組pos中，即pos[p]表示元素a[p]查找的次數，則pos[m]＝cnt；按照二分查找算法思想，第③空為m－1。
16.小明學了排序和查找算法后，編寫了一個處理成績的程序，功能如下：程序運行時，首先從Excel文件中讀取n個學生的技術成績存儲在列表b中，并對列表中的數據按升序進行排序；輸入成績 key，統計并輸出共有多少位同學的成績大于該成績。
實現上述功能的Python程序如下，請在程序劃線處填入合適的代碼。
#從Excel文件中讀取n個學生的技術成績存儲在列表b中，代碼略
n＝len(b)
#對列表b中的元素進行升序排序
for i in range(1，n)：
tmp＝b[i]
j＝0
while ___________________：
j＝j＋1
if j！＝i：
for k in range(i，j，－1)：
　　　　b[k]＝b[k－1]
___________________
print(b)
key＝int(input(″please input key：″))
i，j＝0，n－1
while i<＝j：
m＝(i＋j)∥2
if keyj＝m－1
else：
i＝m＋1
print(″共有″＋___________________＋″位同學大于等于該成績。″)
答案　①jb[j]或jb[j]
②b[k－1]＝tmp或b[j]＝tmp　③str(n－i)
解析　本題主要考查的是排序算法和二分查找算法。本題采用插入排序的方法對列表中的元素進行升序排序，劃線①處while循環的功能是查找當前元素b[i]在前i－1個數中的插入位置，因為是升序排序，因此①處代碼為jb[j]；
②處代碼的功能是將當前元素(bmp)存儲在插入位置(k－1)，因此②處代碼為b[k－1]＝tmp；然后使用二分查找算法在列表b中查找大于key的第一個元素的位置，因為數據是升序排序，因此大于key的元素個數為n－i，由于print命令中使用“＋”運算符，因此需將“n－i”轉換為字符類型，即劃線③處代碼為str(n－i)。課時5　二分查找
課時目標
1.通過實例分析，理解順序查找的基本思想，掌握使用二分查找的一般方法。
2.能根據不同的應用場景，選擇合適的數據結構，能靈活使用二分查找算法編寫程序。
1.二分查找(Binary Search)
二分查找又稱對分查找或折半查找。
二分查找是指在有序的數據序列中，首先將要查找的數據元素與數組的________________元素進行比較，如果相等，則查找成功并退出查找；否則，根據數組元素的有序性，確定新的____________(在數組的前半部分還是在后半部分)；在確定了新的查找范圍后，重復進行以上操作，直到找到或查找結束為止。
①二分查找的前提條件是待查找的數據序列必須有序。
②“未找到”是指當前查找區間不存在，即區間左端點大于右端點。
2.二分查找的算法框架
說明：要查找的目標數據元素為key，待查找的數據元素存放在數組d中。
i、j分別為查找區間的起點位置和終點位置，m為查找區間的中間位置，n為數據元素個數。
i＝0
j＝n－1
while i<＝j：
#計算中點位置m
#比較key與d[m]，并做相應處理
#若i>j，則表示未找到
3.二分查找的程序實現
·設要查找的數據是key，待查找的數據元素存放在數組d中，并已按升序排序。
·輸出查找結果，若找到則輸出信息“找到！位置為：X”，否則輸出“查無此數！”
·輸出查找次數c。
二分查找主要代碼如下(以升序為例)：
輸入key的值
c＝0　　　　　　　#記錄查找次數
find＝False　　　　#設置find的初值
i＝0　　　　　　　#區間左端點位置
j＝n－1　　　　　 #區間右端點位置
while ________________：　#還未找完并且還未找到，則繼續查找
c＝c＋1　　　　#查找次數記數
m＝_________　 #計算中點位置m，等價于m＝int((i＋j)/2)
if key＝＝d[m]：　 #找到目標元素，并進行相應處理
find＝True
print(m)
if key>d[m]：　　#表示要查找的元素比中間位置上的元素大時
i＝m＋1　　　#調整區間左端點
else：　　　　　
j＝m－1　　　#調整區間右端點
if find＝＝False：
print(″查無此數！″)
print(″查找次數為：″，c)
例1 有如下兩組數據：
①1，2，3，4，5，6，7，8，9
②3，4，5，2，1，8，7，6，9
要在上面兩組數據中查找某個特定值，下列說法不正確的是(　　)
A.①②都可以直接使用二分查找
B.①②都可以直接使用順序查找
C.①可以直接使用順序查找，也可以直接使用二分查找
D.②可以直接使用順序查找，但不能直接使用二分查找
聽課筆記：　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
變式訓練　分別使用順序查找算法和二分查找算法在數據序列“5，6，10，13，15，20，21，26，30”中查找數據10，下列關于查找的次數的說法中正確的是(　　)
A.順序查找2次，二分查找3次
B.順序查找3次，二分查找2次
C.順序查找3次，二分查找3次
D.順序查找3次，二分查找4次
例2 在列表lista中存儲的數據依次為：88，78，70，65，60，55，51，45，39，28。現使用二分查找算法在列表lista中查找數據51，共需查找的次數為(　　)
A.1次 B.2次 C.3次 D.4次
聽課筆記：　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
變式訓練　有100個英語單詞已按升序排序并存儲在列表listb中，現要使用二分查找算法在列表listb中查找某個單詞，則最多的查找次數為(　　)
A.5次 B.6次 C.7次 D.8次
例3 某二分查找算法的Python程序段如下：
n＝0; flag＝True
key＝int(input(″輸入要查找的數：″))
i，j＝0，9
while i<＝j and flag：
m＝(i＋j)∥2
if a[m]＝＝key：
flag＝False
elif a[m]i＝m＋1
n＝n＋1
else：
j＝m－1
n－＝1
若列表a中的元素依次是[5，11，18，23，27，33，34，41，45，69]，程序運行后變量n的值是2，則輸入的整數key值不可能是(　　)
A.25 B.34 C.45 D.60
聽課筆記：　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
變式訓練　某二分查找算法的Python程序段如下：
b＝[98，86，81，77，66，60，48，20]
key＝int(input(″key＝″))
i，j＝0，len(b)－1
s＝″″
while i<＝j：
m＝(i＋j)∥2
if b[m]＝＝key：
s＝s＋″M″
break
if keyi＝m＋1
s＝s＋″R″
else：
j＝m－1
s＝s＋″L″
print(s)
程序執行時，輸入key的值為55，則輸出的結果為(　　)
A.RRL B.RLR C.RRLR D.RRLM
例4 有如下 Python 程序段：
def search(i，j)：
　while i<＝j：
　 m＝(i＋j)∥2
　 if a[m]>a[m－1] and a[m]　　　 i＝m＋1
　elif a[m]a[m＋1]:
　　　j＝m－1
　 else：
return m
a＝[3，11，20，25，30，36，50，49，37，16]
print(a[search(0，9)])
程序執行后輸出的結果為(　　)
A.50 B.6 C.7 D.49
聽課筆記：　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
變式訓練　有如下 Python 程序段：
import random
a＝['A'，'#'，'B'，'C'，'D'，'E'，'#'，'F']
i＝0
j＝len(a)－1
x＝random.choice('ABCDEF') #從字符串'ABCDEF'中隨機選出一個字符
while i<＝j：
　　mid＝(i＋j) ∥ 2
　　if a[mid]＝＝x:
　break
　　elif a[mid]＝＝ '#' or a[mid]>x:
　j＝mid－1
　　else：
　i＝mid＋1
print(a[mid])
則程序運行后，輸出結果不可能為(　　)
A.A B.B C.C D.D
1.列表a中存儲了10個數據，依次為2、8、10、16、18、21、25、32、35、43，下列選項中不正確的是(　　)
A.使用順序查找算法查找數據10，共查找了3次
B.使用二分查找算法查找數據10，共查找了3次
C.使用順序查找算法查找數據25，共查找了7次
D.使用二分查找算法查找數據25，共查找了3次
2.在7個有序的數列“a1，a2，a3，a4，a5，a6，a7”中，采用二分查找法查找數值key，依次需要進行比較的數據可能是(　　)
A.a4 B.a4，a6，a2
C.a4，a2，a5 D.a4，a6，a5，a7
3.某對分查找算法的Python程序段如下：
a＝[85，74，70，65，54，36，30，28，26，12]
t＝″″
i，j＝0，9
key＝30
f＝False
while i<＝j and not f：
m＝(i＋j)∥2
t＋＝str(m)
if a[m]＝＝key：
f＝True
elif a[m]>key：
i＝m＋1
t＝t＋″→″
else：
j＝m－1
t＝t＋″←″
執行該程序段，變量t的值是(　　)
A.″4→7←5→″ B.″4→7←5→6→″
C.″4→7←5→6″ D.″4→7→5→6→″
4.某二分查找算法的Python程序段如下：
a＝[125，117，115，108，102，95，88，63，51，36]
key＝108
i，j＝0，len(a)－1
ss＝″″
while i<＝j：
m＝int((i＋j)/2＋0.5)
ss＝ss＋str(m)
if key＝＝a[m]：
break
if keyi＝m＋1
ss＝ss＋″>>″
else：
j＝m－1
ss＝ss＋″<<″
print(ss)
執行該程序段，輸出的內容為(　　)
A.4<<1>>2>>3 　 B.5<<2<<4>>3
C.5<<2>>4<<3 D.5<<2>>4>>3
5.某對分查找算法的Python程序段如下：
n＝len(a)
f＝[0]*n
key＝int(input(″輸入要查找的數：″))
i，j＝0，n－1
while i<＝j：
m＝(i＋j)∥2
f[m]＝1
if a[m]>＝key：
j＝m－1
else：
i＝m＋1
整型數組a為升序序列，輸入待查找數，執行該程序段后，數組f中值為1的元素有3個，則n的值不可能(　　)
A.5 B.8 C.14 D.15
6.有如下Python程序段：
key＝int(input())
i＝0；j＝len(a)－1
s＝″″
while i<＝j：
　　m＝(i＋j＋1)∥2
　　if key＝＝a[m]：
break
　　if keyj＝m－1
　　else：
i＝m＋1
　　s＋＝str(a[m])＋″，″
print(s[：－1])
若數組元素a的值為[6，15，18，20，25，30，35，38，41，46]，輸入正整數key值，執行該程序段，輸出的值可能是(　　)
A.30，20 B.30，41，38
C.25，15，6 D.25，38，41
7.有如下 Python 程序：
import random
a＝[15，18，25，34，38，40，55，61，80，85]
key＝random.randint(15，55)
f＝[0]*10
i＝0；j＝len(a)－1
while i<＝j：
　　m＝(i＋j＋1)∥2
　　if a[m]>key：
　j＝m－1
　else：
　if a[m]%5＝＝0：
　　　f[m]＝1
　i＝m＋1
執行該程序段后，列表 f 值可能是(　　)
A.[0，0，1，0，0，1，0，0，0，0]
B.[0，0，0，0，0，1，0，0，1，0]
C.[1，0，1，0，0，0，0，0，0，0]
D.[0，0，0，0，0，1，1，0，0，0]
8.有如下 Python 程序段：
def binSearch(i，j，key)：
　if i>j：
　return－1
　m＝(i＋j)∥2
　if key＝＝a[m]：
　 return m
　if key　return binSearch(i，m－1，key)＋m
　return binSearch(m＋1，j，key)＋m
n＝7
a＝[5，6，7，8，9，9，11]
key＝int(input(″輸入查找鍵：″))
print(binSearch(0，n－1，key))
執行該程序段后，輸入待查找的數，輸出的結果不可能是(　　)
A.6 B.8 C.12 D.14
課時5　二分查找
知識梳理
1.中間位置　查找范圍
3.i<＝j and not find　(i＋j)∥2
例題精析
例1　A　[本題主要考查的是使用順序查找和對分查找的適用條件。順序查找對待查找的數據沒有要求，而二分查找的前提是數據必須有序。①中數據有序，②中數據無序，①中數據順序查找和二分查找均可以直接使用，②中數據只能使用順序查找，若要使用二分查找，則先對②中數據進行排序操作。因此，不正確的是A，答案為A。]
變式訓練　C　[本題主要考查的是順序查找和二分查找的算法思想。數據10是數據序列中第3個元素，因此使用順序查找時，共查找次數為3次，使用二分查找時，依次被訪問的數據為15、6、10，即二分查找的次數也為3次。因此，答案為C。]
例2　D　[本題主要考查的是二分查找的查找過程。第一次找到的索引號為4的數據(60)，因為51<60，因此向右查找，第二次找到索引號為7的數據(45)，因為51>45，因此向左查找，第三次找到索引號為5的數據(55)，因為51<55，因此向右查找，第四次找到索引號為6的數據(51)，找到要找的數據后結束查找，因此共查找了4次，答案為D。]
變式訓練　C　[本題主要考查的是計算二分查找的查找次數。N個數據，使用二分查找，查找次數最多為log2(n)取整加1，現共有100個單詞，因此最多次數為7次，答案為C。]
例3　B　[本題主要考查二分查找算法。用二叉搜索樹畫出各個元素的搜索順序，圖中各個左子樹方向可以讓n自減，右子樹方向可以讓n自增。
A選項，若key＝25，則從節點23的右側出循環，此時m、n的值是3、2，同理key＝45, m、n的值是8、2，key＝60，m、n的值是9、2。key＝34，m、n的值是6、1。]
變式訓練　A　[本題主要考查的是二分查找時的方向問題。本題的功能是求使用二分查找在降序序列中查找數據55的過程，如果找到，則記為“M”，如果要查找的數據在序列的右邊區間中，則記為“R”，否則記錄為“L”。因此，答案為A。]
例4　A　[本題考查二分查找以及其變式。a[m－1]，a[m]，a[m＋1]如果是連續上升的序列，往后找 i＝m＋1 a[m－1]，a[m]，a[m＋1]如果是連續下降的序列，往前找 j＝m－1，a[m－1]，a[m]，a[m＋1]如果不滿足連續上升或者下降，則直接輸出m。]
變式訓練　B　[本題考查二分查找的算法思想。根據題目要求，畫出相應的二叉樹，當找到#號時，向左查找，因此不可能找到B。]
隨堂檢測
1.D　[本題主要考查的是順序查找和二分查找算法思想。使用二分查找算法查找數據25，需要的查找次數為4次，因此D選項不正確，答案為D。]
2.A　[本題考查二分查找的算法思想。第1次查找的是最中間的節點a4，因此A選項正確。B選項a2比a4小，查找到a6后，不可再去找a2。C選項a5比a4大，也不可能。D選項第3次查找，要么a5或a7，不可能2個數同時被查找到。]
3.C　[本題主要考查的是二分查找的程序實現。本題的功能是在一個降序數列中查找key的過程，記錄每次訪問的元素，并標識查找的方向(向右→或向左←)。在數列中查找30的過程中，第一次查找時，m＝4，t＝“4”，因為a[4]＝54>key，因此向右查找，i＝5，t＝“4→”；第二次查找時，m＝7，t＝“4→7”， 因為a[7]＝28key，因此向右查找，i＝6，t＝“4→7←5→”；第四次查找時，m＝6，t＝“4→7←5→6”， 因為a[6]＝＝key，因此查找結束，故答案為C。]
4.C　[本題主要考查的是二分查找的變式。本題中將中間位置m的計算公式修改為m＝int((i＋j)/2＋0.5)，即在偶數個數的區間中，找到的m為中間靠右的位置，因此，在查找數據108的過程中，依次訪問的元素位置為5、2、4、3，注意左右方向的表示。查找結束時，字符串ss的內容為5<<2>>4<<3，答案為C。]
5.D　[本題考查對分查找的次數。本題為對分查找，數組f標記查找過的下標，若為3，表明共查找了3次。而該題中，查找找到不退出，退出的唯一條件是j。我們可以根據選項n的數量畫出二叉判定樹，若不存在從第三層結束的可能，就是不可能選項。]
6.B　[根據二分查找算法畫出對應的二叉樹為，可以得到遍歷的路徑。]
7.D　[考查二分查找算法的算法思想。f[m]賦值語句的執行條件 a[m]<＝key and a[m]%5＝＝0，即向右查找過程中，節點是5的倍數。產生數的范圍是[15，55]，那么只可能查找[40，55]之間的數，第1次向右查找的節點為40，第2次查找的節點是55，即只能查找55。]
8.B　[本題考查遞歸法求二分查找，找到后返回中間位置，沒有找到，累加找過的位置m。用索引位置畫出二叉樹為，沒有一條分支節點和為8。]

展開更多......

收起↑