資源簡介

專題18　查找算法
學業要求 知　識　點 學業水平等級
1.掌握對分查找的核心算法思想并用程序代碼實現 4
2.掌握利用二叉樹來描述查找的路徑或區間 4
知識點一　二分查找的算法思想
【知識梳理】
1.________又稱檢索，計算機根據所給條件查找出滿足條件的對象，即在存儲的一批數據內尋找出一個特定的數據，或者確定在該批數據內是否存在這樣的數據。若沒有找到滿足條件的對象，則返回特定值，表明查找失?。蝗舨檎业綕M足條件的對象，則表明查找成功，一般要求返回該對象的存儲位置或對象值本身。
2.________________又稱線性查找，從順序表的一端開始，依次將每個元素的關鍵字與給定值key(查找鍵)進行比較。若某個元素的關鍵字等于key，則表明查找成功；若所有元素都比較完畢仍找不到，則表明查找失敗。
3.________________又稱折半查找，對分查找。它是一種效率很高的查找算法，但被查找的數據序列必須是有序的。
4.二分查找首先將查找鍵與____________處于________的元素進行比較，如果中間位置上的元素的數值與查找鍵不同，根據數組元素的有序性，就可確定在數組的________還是________繼續查找；在新確定的范圍內，繼續按上述方法進行查找，直到獲得最終結果。
5.二分查找算法描述：在一個區間為[i，j]的有序數據序列a中查找一個數據key，先確定區間的中間位置m，讓key與a[m]比較，若兩者相等，表示找到數據，結束查找；若中間位置的數a[m]不是要查找的數，把區間分為[i，m－1]和[m＋1，j]兩部分。若查找的數據在右半段，修改左邊界i的值為m＋1，繼續往右查找；若查找的數據在左半段，修改右邊界j的值為m－1，繼續往左查找；修改邊界后，若i大于j，則查找的區間為空，等式i＝j＋1肯定成立，則該數在序列中不存在。
【經典案例】
二分查找中間位置m的計算公式為m＝(i＋j)//2和m＝(i＋j＋1)//2，當i＋j為奇數時，兩者沒有區別；當i＋j為偶數時，中間位置有兩個，前者是中間偏左，后者是中間偏右。利用判定二叉樹快速解題，同時確定查找路徑。當查找中間結點時，還可以繼續查找，因此查找不成功一定發生在葉子結點。在查找一個數的路徑確定每次查找的數位置和值，可以判斷查找次數，若在找不到該數據時，可以判斷此時變量i、j和m的值。大致可以分為以下幾種情況：①隨機給出查找值，求查找次數或查找路徑；②給出查找次數或查找路徑，求查找值的范圍；③當查找成功時沒有結束查找，求查找次數或查找的邊界值。
【例1】 有如下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。
聽課筆記：____________________________________________________________
______________________________________________________________________
______________________________________________________________________
【變式1】 有如下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
該程序段運行后，列表lst的長度不可能為(　　)
A.1 B.2
C.3 D.4
【例2】 有如下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]
思維點撥
明考向 本題考查二分查找算法的算法思想
精點撥 f[m]賦值語句的執行條件a[m]<＝key and a[m]%5＝＝0，即向右查找過程中，節點是5的倍數。產生數的范圍是[15，55]，那么只可能查找[40，55]之間的數，第1次向右查找的節點為40，第2次查找的節點是55，即只能查找55
聽課筆記：_____________________________________________________________
______________________________________________________________________
______________________________________________________________________
【變式2】 有如下Python程序段：
import random
a＝[1，3，3，8，8，10，10，14，16，17]
key＝random.randint(0，9)*2
ans＝－1；f＝0
L＝0；R＝9
while L<＝R：
m＝(L＋R＋1)//2
if a[m]＝＝key：
ans＝m
break
if a[m]>key：
R＝m－1
f－＝1
else：
L＝m＋1
f＋＝1
運行該程序段后，關于f和ans的結果，下列說法正確的是(　　)
A.f可能的最小值為－3
B.f的值可能為－1
C.ans的值可能為1
D.ans的值不可能為3
知識點二　極值查找
【知識梳理】
1.查找結束可能是2種情況，一是當a[m]和key相等時，找到要查找的元素，采用________語句退出循環，二是查找的區間________存在，即左區間i大于右區間j。
2.在一個非降序序列中查找一個不存在的數key時，查找的區間不斷地縮小，最后一次查找時，區間中只有________個元素，即左區間i等于右區間j。若a[m]大于key，則移動右區間j，左區間i保持不變，此時變量j＝i－1；若a[m]小于key，則移動左區間i，右區間保持j不變，此時變量i＝j＋1。因此二分查找算法結束后，若查找的數據不存在，肯定有i＝________的等量關系。
3.當一個非降序序列中存在多個與key相等的數據時，若要找到第1個小于key或者最左邊的key，稱為左極值，算法為：當a[m]________于key時，并沒有采用break語句退出循環，而是繼續向左查找，由于找到后，j向左移動，因此j不可能指向key，最左邊key位置為i。
4.右極值指的是要找到第1個大于key或者最右邊的key，算法為：當a[m]等于key時，繼續向________查找，由于找到后，i向右移動，因此i不可能指向key，最右邊key位置為j。
【經典案例】
當一個非降序序列中存在多個連續相等的數據key時，若要查找最左邊key，設置的查找條件為當a[m]＝＝key時，還需移動j為m－1繼續向左查找，當i>j即i＝j＋1時，查找的區間不存在，此時j指向的就是第1個小于等于key的值；若要查找最右邊的key，當查找成功時，還需移動i為m＋1繼續向右查找，此時i指向的就是第1個大于等于key的值。
【例題】 某對分查找算法的Python程序如下：
left＝0；right＝7；s＝″″
d＝[14，23，29，34，38，42，52，69]
key＝int(input('請輸入要查找的數據'))
while left<＝right：
mid＝(left＋right)//2
if key＝＝d[mid]：
　 　　s＝s＋″M″
if key<＝d[mid]：
　 　　right＝mid－1；s＝s＋″L″
else：
　 　　left＝mid＋1；s＝s＋″R″
該程序段執行后，顯示的內容可能是(　　)
A.RRRML B.LM
C.LMRL D.LRRM
思維點撥
明考向 根據算法畫出二叉樹如圖所示找到后并不結束循環
精點撥 A 查找數據69，查找路徑34，42，52，3次向右移動，第4次找到了
B 查找數據23，但是找到23后，還是要向左查找，直至區間不存在，即LMLR
C 查找數據23，但是找到23后，還是要向左查找，不是向右查找
D 向左找到23，向右找到29，再向右查找比29大比34小的數，不可能再次向右查找
聽課筆記：_____________________________________________________________
______________________________________________________________________
______________________________________________________________________
【變式】 某Python程序段如下：
import random
a＝[0]*8；a[0]＝1
for i in range(1，8)：
a[i]＝a[i－1]＋random.randint(1，10)
n＝0；key＝5
i，j＝0，7
while i<＝j：
m＝(i＋j)//2；n＋＝1
if a[m]<＝key：
　　 　　i＝m＋1
else：
　　　　 j＝m－1
print(n)
執行該程序段后，輸出的結果是(　　)
A.1 B.2
C.3 D.4
1.在7個有序的數列“a1，a2，a3，a4，a5，a6，a7”中，采用二分查找法查找數值key，依次需要進行比較的數據可能是(　　)
A.a4 B.a4，a6，a2
C.a4，a2，a5 D.a4，a6，a5，a7
2.有如下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 keyj＝m－1
else：
i＝m＋1
print(i，j，m，n)
執行該程序段后，下列說法正確的是(　　)
A.n的值可能為4
B.若n值為2，則必定滿足i<＝j
C.m的值可能為1
D.若n值為3，則key的值可能是45
3.有如下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)
程序運行后，變量p的值不可能是(　　)
A.2 B.3
C.4 D.5
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
5.某對分查找的Python程序如下：
from random import randint
a＝[19，17，16，14，13，11，9，7]
key＝randint(0，4)*2＋9
i＝0；j＝7；c＝0
while　i<＝j：
c＝c＋1
m＝(i＋j)//2
if a[m]>key：
i＝m＋1
else：
j＝m－1
該程序段執行后，下列說法不正確的是(　　)
A.j的值可能為1 B.c的值一定等于3
C.i的值一定等于j＋1 D.i的值一定不等于7
6.某二分查找算法的Python程序如下：
import random
key＝random.randint(0，4)*2＋5
n＝10
ans＝0
a＝[4，5，5，8，9，11，11，13，15，17]
i＝0
j＝n－1
while i<＝j：
m＝(i＋j)//2
if a[m]<＝key：
i＝m＋1
else：
j＝m－1
ans＋＝a[m]
print(ans)
程序運行后，輸出ans的值不可能是(　　)
A.19 B.27
C.37 D.44
7.如下Python程序實現的功能是：在非遞增數組a中查找最后一個大于等于key的元素下標。
#讀取一批非遞增的數據保存在數組a中，代碼略
key＝int(input(″請輸入待查找的數據：″))
L，R＝0，len(a)－1
while L<＝R：
m＝(L＋R)//2
if ①________：
L＝m＋1
else：
②________
if R＝＝－1：
print(″不存在大于等于%d的數″%key)
else：
print(f″最后一個大于等于%s的元素下標是%d″%(key，③________))
劃線處的內容是(　　)
A.①a[m]>key　　　②R＝m　　?、踡
B.①a[m]>key ②R＝m－1 ③m
C.①a[m]>＝key ②R＝m－1 ③R
D.①a[m]>＝key ②R＝m ③R
8.某Python程序如下：
a＝[86，75，58，46，20，18，12，5]
key＝int(input())
n＝0；i＝0；j＝len(a)－1
while i<＝j：
m＝(i＋j)//2
if key>a[m]：
j＝m－1；n＝n－1
else：
i＝m＋1；n＝n＋1
當輸入不同的 key 值，運行該程序段后，n的值可能有(　　)
A.5種 B.6種
C.7種 D.8種
專題18　查找算法
知識點一
知識梳理
1.查找(Search)
2.順序查找(Sequential Search)
3.二分查找(Binary Search)
4.有序數組內　中間位置　前半部分　后半部分
經典案例
例1　B
變式1　D　[本題考查二分查找。畫出二叉樹，隨機生成[20，70]區間內的一個正整數，最少查找1次，最多4次，但查找大于76的數時，才要查找4次。每查找一次，將查找的區間添加到lst中，所以長度4次是不可能的。]
例2　D
變式2　D　[查找一個0～18之間的隨機偶數key，畫出相應的二叉樹。A選項查找0，向左查找4次，f的值為－4。B選項向右查找1次，找到的數為3，不是偶數。C選項a[1]的值為3，不是偶數。D選項ans的值若為3，a[3]的值為8，而找到的第1個8的索引位置是4。]
知識點二
知識梳理
1.break　不　2.一　j＋1　3.等　4.右
經典案例
例題　A
變式　C　[本題考查二分查找。根據題意畫出判定二叉樹如圖所示。如果條件a[m]<＝key成立，還要向右繼續查找，因此除了查找大于等于a[6]的數據，均要查找3次，a[0]的值1，隨機產生一個比前一項至少大1的數，因此a[6]至少是7，只需找3次。]
當堂過關檢測
1.A　[本題考查二分查找的算法思想。第1次查找的是最中間的節點a4，因此A選項正確。B選項a2比a4小，查找到a6后，不可再去找a2。C選項a5比a4大，也不可能。D選項第3次查找，要么a5或a7，不可能2個數同時被查找到。]
2.B　[本題考查二分查找算法思想。key是[40，70]區間的偶數，n是循環次數。畫出相應的二叉樹。最多查找3次；a[1]為37，查找的位置不可能是1。若查找2次，說明查找的數是50，中間退出循環，滿足條件i<＝j。]
3.B　[本題考查索引排序和二分查找算法。key值在30－60，在列表a中只有40、59、32符合范圍，對應的索引值為2、4、5。]
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。]
5.A　[本題考查二分查找算法思想。數組a為降序數列，key的取值范圍是9～17之間的奇數，當找到key時不要向左繼續查找，結束查找時，j小于i，且i等于j＋1，位置i是最接近要查找的。A選項查找17，j的值為0，查找15，j的值為2。D選項key最小值是9，因此i的值最大值是6。]
6.A　[本題考查二分查找算法。變量key的值可能是[5，7，9，11，13]，ans是查找值的累加和。當找到key時，還要向右邊界繼續查找。當key＝5、7時，a[m]分別是：9、5、5、8，ans＝27，由此可以推斷不可能是19。]
7.C　[查找最后一個大于等于該數應該是查找右極值，即找到后還要向右查找。最終R指向是要查找的數。]
8.A　[本題考查二分查找。中點計算方式為左偏，查找二叉樹如下：
變式在于相等不退出，而是繼續向右找，key為任意數，無論是否找到，最終都從虛線處走出。向左加1，向右減1，分析二叉樹可知，n值可能為：－3，－1，1，2，4這5種。]

展開更多......

收起↑