資源簡(jiǎn)介

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

展開更多......

收起↑