資源簡介

專題12　查找算法
學習目標　
1.掌握對分查找核心算法思想，在一個[i，j]區間中，不斷查找中間位置m，并不斷更新查找區間(更新并畫出左右端點)，直到找到或區間不存在；
2.掌握利用退出語句、標志變量和循環條件不成立的結束循環兩種方式；
3.掌握查找區間不存在時，根據查找鍵值來判斷變量i、j、m的關系.
在一個區間為[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肯定成立，則該數在序列中不存在。
(2024年1月浙江省選考)某算法的部分流程圖如圖所示，若n的值為7，key的值為78，數組元素a[0]至a[n－1]依次存放7，12，24，36，55，78，83，執行這部分流程后，輸出c的值為(　　)
A.0 B.1 C.2 D.3
重難點1　二分查找的算法思想
若題目是要查找的數key已知，采用列表法比較快，用表格列出每次查找數組d的區間開始位置i、j和比較數的位置m及值a[m]，模擬對分查找的過程。中間位置m的計算公式為m＝(i＋j)∥2和m＝(i＋j＋1)∥2，當i＋j為奇數時，兩者沒有區別；當i＋j為偶數時，中間位置有兩個，前者是中間偏左，后者是中間偏右。
例1 在存儲8個非降序元素的數組a中，查找key的代碼如下，
key＝int(input(″輸入要查找的數據：″))
i＝0；j＝len(a)－1
f＝[0]*len(a)
while i<＝j：
　　m＝(i＋j)∥2
　　f[m]＝1
　　if key＝＝a[m]：
　 break
　　if key　 j＝m－1
　　else：
　 i＝m＋1
print(f)
運行該程序，輸出的結果可能是(　　)
A.[1，1，0，1，0，0，0，0] B.[1，1，1，1，0，0，0，0]
C.[0，0，1，1，0，0，0，0] D.[0，0，0，1，1，0，1，0]
變式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
例2 運行如下Python程序段，若輸入“B”，則變量cnt的值為(　　)
a＝['A', 'B', 'C', 'D', 'E', 'F', 'G']
ch＝input(″輸入A－G之間的字母：″)
cnt＝0
for key in a：
　 i，j＝0，len(a)－1
　 while i<＝j：
　 m＝(i＋j)∥2
　　　if a[m]＝＝ch：
　　　 cnt＋＝1；break　#終止while循環
　 if a[m]＝＝key：
　　　 break
　 elif a[m]　　　 i＝m＋1
　 else：
　　　 j＝m－1
A.1 B.2 C.3 D.7
變式2 有如下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)
輸入36，執行程序后，輸出結果是(　　)
A.1 B.2 C.3 D.4
重難點2　極值查找
當一個非降序序列中存在多個連續相等的數據key時，若要查找最左邊key，設置的查找條件為當a[m]＝＝key時，還需移動j為m－1繼續向左查找，當i>j即i＝j＋1時，查找的區間不存在，此時j指向的就是第1個小于等于key的值；若要查找最右邊的key，當查找成功時，還需移動i為m＋1繼續向右查找，此時i指向的就是第1個大于等于key的值。
例題 某二分查找算法的Python 程序段如下：
a＝[1，3，5，7，8，8，8，10，12]
import random
key ＝ random.randint(1, 20)
i ＝ 0; j ＝ 8; s ＝″″
while i <＝ j：
　 m ＝ (i ＋ j) ∥ 2
　 if a[m] > key：
　 j ＝ m － 1; s ＝ s ＋″L″
　else：
　 i ＝ m ＋ 1; s ＝ s ＋″R″
執行該程序段后，輸出內容可能是(　　)
A.LR B.LLL
C.RLR D.RRRR
變式 有如下Python程序段：
import random
def binary(L，R，key)：
　　m＝(L＋R)∥2
　　if L>R：
　 return R
　　if key<＝a[m]：
　 return binary(m＋1，R，key)
　　else：
　 return binary(L，m－1，key)
a＝[9，8，7，7，7，5，5，3]
x＝random.randint(1，4)*2＋1
print(binary(0，7，x))
執行該程序段后，輸出結果不可能是(　　)
A.1 B.4 C.6 D.7
重難點1　二分查找的算法思想
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程序段，輸入正整數key值，執行該程序段，輸出的值可能是(　　)
a＝[6，15，18，20，25，30，35，38]
key＝int(input(″輸入要查找的數據：″))
i＝0；j＝len(a)－1
s＝″″
while i<＝j：
　 m＝(i＋j＋1)∥2
　 s＋＝str(a[m])＋″，″
　 if key＝＝a[m]：
　 break
　 if key　 j＝m－1
　 else：
　 i＝m＋1
print(s[：－1])
A.25，20 B.25，18，20
C.25，15，6 D.25，30，35
3.有如下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] < target:
　 left ＝ mid ＋ 1
　　elif nums[mid] > target:
　 right ＝ mid － 1
該程序段運行后，列表lst的長度不可能為(　　)
A.1 B.2 C.3 D.4
4.有如下Python程序段：
import random
def find(x，y，key)：
　 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，key)
a ＝ [2，4，6，8，10，12，14，16]
key＝random.choice(a)　#從序列的元素中隨機挑選一個元素
print(find(0，len(a)－ 1，key))
上述程序執行完后，函數 find 被調用的最多次數是(　　)
A.3 B.4 C.5 D.6
5.某二分查找算法的程序段如下：
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
執行該程序段后，下列說法正確的是(　　)
A.該程序若要實現二分查找，要求數組a按降序排列
B.若n為－2，則查找key值可能等于a[3]的值
C.若n為2，則查找 key 的值可能小于a[10]
D.n的值最小為－4，最大為4
6.如下 Python 程序段：
import random
a＝[1，3，5，7，9，11，13，15]
key＝random.randint(1，8)*2
i，j＝0，len(a)－1
s＝0
while i<＝j：
　 m＝(i＋j＋1)∥2
　 if a[m]＝＝key：
　 break
　 if a[m]>key：
　　　j＝m－1；s－＝1
　 else：
　 i＝m＋1；s＋＝1
print(s)
上述程序執行完以后，s 的值可能有(　　)
A.4 種 B.5種 C.7種 D.8 種
重難點2　極值查找
1.某二分查找算法的 Python 程序段如下：
import random
key＝random.randint(1，4)*2
a＝[2，3，4，4，4，6，7，10]
ans＝0；i＝0；j＝len(a)－1
while i<＝j：
　 m＝(i＋j)∥2
　 if key>＝a[m]：
　 i＝m＋1
　 else：
　 j＝m－1
　 ans＋＝a[m]
print(ans)
執行該程序段后，ans 的值不可能是(　　)
A.27 B.14 C.11 D.9
2.有如下Python程序段：
a ＝ [15, 20, 32, 32, 54, 66, 94, 96]
f ＝ [0] * len(a)
key ＝ 2 * random.randint(10, 47) ＋ 1
i ＝ 0; j ＝ len(a) － 1; s ＝ 0; n ＝ 0
while i <＝ j：
　　m ＝ (i ＋ j ＋ 1) ∥ 2
　　f[m] ＝ 1
　　if key <＝ a[m]：
　 j ＝ m － 1; n ＝ n － 1
　　else：
　 i ＝ m ＋ 1; n ＝ n ＋ 1
s ＝ sum(f)
執行該程序段后，下列說法正確的是(　　)
A.變量i的值可能為3
B.變量n的值可能為3
C.變量s的值一定為3
D.變量f的值可能為[1，0，1，0，1，0，0，0]
3.有如下Python程序段：
#隨機產生10個整型元素的非降序序列，依次存入列表a(a[0]！＝a[9])，代碼略
a＝[]
key＝int(input())
i＝0；j＝9
n＝0
while i<＝j:
　　m＝(i＋j)∥2
　　n＋＝1
　　if a[m]　 i＝m＋1
　　else：
　 j＝m－1
執行上述程序段后，下列說法不正確的是(　　)
A.a[i＋1]可能等于key
B.a[j]可能等于key
C.i一定等于j＋1
D.n的值一定大于2
4.如下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　　 ③m
B.①a[m]>key　　②R ＝ m－1　③m
C.①a[m]>＝key　②R ＝ m－1　③R
D.①a[m]>＝key　②R ＝ m　　 ③R
重難點1　二分查找的算法思想
1.某二分查找算法的 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
2.某二分查找算法的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
數組a中的元素各不相同且按降序排列，執行該程序段后n的值為4，則key的值不可能為(　　)
A.a[1] B.a[4] C.a[12] D.a[16]
3.有如下 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
4.有如下 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
5.如下 Python 程序段：
#導入模塊并隨機產生8個整型元素的非降序的奇數序列，并依次存入列表a[0]至a[7]，代碼略
key＝random.randint(1，20)
i＝0；j＝7；s＝0
while i<＝j：
　　m＝(i＋j＋1)∥2
　　if a[m]＝＝key：
　 break
　　if a[m]>key：
　 j＝m－1
　 else：
　 i＝m＋1
　s＋＝ 1
執行上述程序段后，下列說法不正確的是(　　)
A.a[j]可能小于a[i]＋2
B.a[i]可能等于key
C.i一定等于j＋1
D.s的值一定小于等于4
6.有如下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)
執行該程序段后，下列說法正確的是(　　)
A.n的值可能為4
B.若n值為2，則必定滿足i<＝j
C.m的值可能為1
D.若n值為3，則key的值可能是45
7.某二分查找算法的程序如下：
i ＝ 0; j ＝ 9; c ＝ 0
key ＝ int(input())
while i <＝ j：
　　m ＝ (i ＋ j) ∥ 2
　　if a[m] ＝＝ key：
　 break
　　if a[m] > key：
　 j ＝ m － 1
　　else：
　i ＝ m ＋ 1
　c ＋＝ 1
若a＝[2，13，14，19，23，26，29，31，32，38]，運行該程序段后，c的值為2，則key的值不可能是(　　)
A.19 B.29 C.30 D.32
8.班里共n位同學，學號0至n－1，其中有一位同學未交作業。為了找出未交作業的同學學號，假設已交作業的n－1位同學學號從小到大存放于列表a中，則劃線處代碼是(　　)
L，R＝0，n－2
while L<＝R：
　 m＝(L＋R)∥2
　 if a[m]＝＝m：
　 ①________
　 else：
　 ②________
print(③________)
A.①R＝m－1　②L＝m＋1　③L
B.①R＝m－1　②L＝m＋1　③R
C.①L＝m＋1　②R＝m－1　③L
D.①L＝m＋1　②R＝m－1　③R
9.有如下Python程序段：
def find_base(x，y)：
　 left, right ＝ 2, 10
　 while left <＝ right：
　 mid ＝ (left ＋ right) ∥ 2
　 value ＝ calc(mid, y)　#calc函數將mid進制的整數y轉化為十進制數
　 if value ＝＝ x：
　　　 return mid
　 elif value < x：
　　　 left ＝ mid ＋ 1
　 else：
　　　 right ＝ mid － 1
　　return －1
x ＝ int(input()) ; y ＝ int(input())
print(find_base(x，y))
執行該程序段后，依次輸入83和123，程序輸出為(　　)
A.2 B.6 C.8 D.－1
10.有如下 Python 程序段：
def binSearch(i，j，key)：
　 if i>j：
　 return 0
　 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
11.有如下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
12.小明為英文字母A～Z定義了一套全新的二進制編碼規則，代碼如下
s＝[chr(i＋65)for i in range(26)]
dc＝{}
for k in s：
　 i，j＝0，len(s)－1
　 rt＝″0″
　 while i<＝j：
　 m＝(i＋j)∥2
　 if s[m]＝＝k：
　　　 dc[k]＝rt
　　　 break
　 elif s[m]　　　 i＝m＋1
　　　 rt＋＝″1″
　 else：
　　　 j＝m－1
　　　 rt＋＝″0″
inp＝input(″請輸入英文字符串：″).upper()#將輸入的英文字母轉為大寫
for c in inp：
　 print(dc[c], end＝″″)
當程序運行后，輸入“OK”后，其輸出的二進制編碼為(　　)
A.01001 0011 B.01001 000
C.00001 0011 D.01001 00110
重難點2　極值查找
1.有如下Python程序段：
from random import randint
k＝randint(0，2)*2
i＝0；j＝6；cnt＝0
while i<＝j：
　　cnt＝cnt＋1
　　m＝(i＋j)∥2
　　if a[m]＝＝a[k]：
　 break
　　if a[m]　 i＝m＋1
　　else：
　 j＝m－1
數組元素 a[0]到 a[6]各不相同且按升序排列，執行該程序段，下列說法不正確的是(　　)
A.m的值不可能為6
B.cnt的值一定為3
C.變量 i、j的值一定相同
D.i的值可能小于m
2.某二分查找算法的Python程序段如下：
#生成若干數據有序排列后存儲在列表d，代碼略
n＝0
i，j＝0，len(d)－1
while i<＝j：
　　m＝(i＋j)∥2
　　print(d[m]，end＝″ ″)
　　if d[m]＝＝key：
　 break
　　elif d[m]　　　 i＝m＋1
　　else：
　　　 j＝m－1
　　　 n＋＝1
程序運行后，變量n的值為2，輸出的內容可能是(　　)
A.4 7 7 B. 10 4 12
C.7 6 7 D.9 12 15 18
3.有如下 Python 程序段：
a＝[34，35，38，41，41，41，45，45，69，78]
key＝41；n＝0
i＝0；j＝9
while i<＝j：
　　m＝(i＋j)∥2
　　if key　 j＝m－1
　　else：
　 i＝m＋1
該程序段運行結束后，下列說法正確的是(　　)
A.i的值是3 B.j的值是3
C.i的值是6 D.j的值是6
4.有如下 Python 程序段：
import random
a ＝ [1，3，4，6，6，6，9，9，11，12]
key ＝ random.randint(2，5) * 2
i，j ＝ 0，9
while i <＝ j：
　 m ＝ (i ＋ j) ∥ 2
　 if key < a[m]：
　 j ＝ m － 1
　 else：
　 i ＝ m ＋ 1
print(j)
執行該程序段后，輸出的結果不可能是(　　)
A.2 B.3 C.5 D.7
5.某二分查找算法的Python程序如下：
#隨機產生包含20個整型元素的升序序列，依次存入數組a，代碼略
i＝0；j＝19；s＝″″
key＝int(input())
while i<＝j：
　　m＝(i＋j)∥2
　　s＋＝str(m)＋″，″
　　if a[m]>key：
　 j＝m－1
　　else：
　 i＝m＋1
執行上述程序并輸入待查找數據，程序執行后，s的值不可能為(　　)
A.″9，4，1，0，″ B.″9，4，1，2，3，″
C.″9，4，6，5，″ D.″9，14，11，10，12，″
6.有如下Python程序：
a＝[0，20，23，23，24，24，31，48，49，73，75]
key＝int(input())
c＝0
i，j＝1，10
while i<＝j:
　 m＝(i＋j)∥2
　 if a[m]<＝key:
i＝m＋1
　 else:
j＝m－1
　 c＋＝1
print(c)
若程序運行后，輸出的結果是 3，則輸入的key可能是(　　)
A.20或73 B.24或49
C.23或24 D.23或49
專題12　查找算法
學習目標　
1.掌握對分查找核心算法思想，在一個[i，j]區間中，不斷查找中間位置m，并不斷更新查找區間(更新并畫出左右端點)，直到找到或區間不存在；
2.掌握利用退出語句、標志變量和循環條件不成立的結束循環兩種方式；
3.掌握查找區間不存在時，根據查找鍵值來判斷變量i、j、m的關系.
在一個區間為[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肯定成立，則該數在序列中不存在。
(2024年1月浙江省選考)某算法的部分流程圖如圖所示，若n的值為7，key的值為78，數組元素a[0]至a[n－1]依次存放7，12，24，36，55，78，83，執行這部分流程后，輸出c的值為(　　)
A.0 B.1 C.2 D.3
答案　B
解析　本題考查二分查找算法。變量c表示移動左邊界向右查找的次數。查找78的過程為先找到36，向查查找1次，找到78，結束查找。
重難點1　二分查找的算法思想
若題目是要查找的數key已知，采用列表法比較快，用表格列出每次查找數組d的區間開始位置i、j和比較數的位置m及值a[m]，模擬對分查找的過程。中間位置m的計算公式為m＝(i＋j)∥2和m＝(i＋j＋1)∥2，當i＋j為奇數時，兩者沒有區別；當i＋j為偶數時，中間位置有兩個，前者是中間偏左，后者是中間偏右。
例1 在存儲8個非降序元素的數組a中，查找key的代碼如下，
key＝int(input(″輸入要查找的數據：″))
i＝0；j＝len(a)－1
f＝[0]*len(a)
while i<＝j：
　　m＝(i＋j)∥2
　　f[m]＝1
　　if key＝＝a[m]：
　 break
　　if key　 j＝m－1
　　else：
　 i＝m＋1
print(f)
運行該程序，輸出的結果可能是(　　)
A.[1，1，0，1，0，0，0，0] B.[1，1，1，1，0，0，0，0]
C.[0，0，1，1，0，0，0，0] D.[0，0，0，1，1，0，1，0]
思維點撥
明考向 本題考查二分查找算法的程序實現。根據題意，畫出查找的二叉樹如圖所示，當找到某個數字時，數組f中該數字對應索引位置上值賦值為1
精　點　撥 A 分別訪問索引3，1，0
B 分別訪問索引3，2，1，0，但該路徑不存在
C 分別訪問索引3，2，該路徑也不存在
D 分別訪問索引3，4，6，該路徑也不存在
答案　A
變式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
解析　本題考查二分查找的算法思想。根據題目要求，畫出相應的二叉樹，當找到#號時，向左查找，因此不可能找到B。
例2 運行如下Python程序段，若輸入“B”，則變量cnt的值為(　　)
a＝['A', 'B', 'C', 'D', 'E', 'F', 'G']
ch＝input(″輸入A－G之間的字母：″)
cnt＝0
for key in a：
　 i，j＝0，len(a)－1
　 while i<＝j：
　 m＝(i＋j)∥2
　　　if a[m]＝＝ch：
　　　 cnt＋＝1；break　#終止while循環
　 if a[m]＝＝key：
　　　 break
　 elif a[m]　　　 i＝m＋1
　 else：
　　　 j＝m－1
A.1 B.2 C.3 D.7
思維點撥
明考向 本題考查二分查找的算法實現
精點撥 由7個字母構成一個搜索二叉樹，如圖所示，遍歷樹中每個節點，若搜索路徑包含字母ch，則cnt的值增加1，查找BAC時包含字母B的節點個數
答案　C
變式2 有如下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)
輸入36，執行程序后，輸出結果是(　　)
A.1 B.2 C.3 D.4
答案　C
解析　本題考查二分查找。程序的功能是數組a的i索引前找一個數，滿足a[i]*a[m]＝＝n的個數，因此分別是9*4、12*3、18*2。
重難點2　極值查找
當一個非降序序列中存在多個連續相等的數據key時，若要查找最左邊key，設置的查找條件為當a[m]＝＝key時，還需移動j為m－1繼續向左查找，當i>j即i＝j＋1時，查找的區間不存在，此時j指向的就是第1個小于等于key的值；若要查找最右邊的key，當查找成功時，還需移動i為m＋1繼續向右查找，此時i指向的就是第1個大于等于key的值。
例題 某二分查找算法的Python 程序段如下：
a＝[1，3，5，7，8，8，8，10，12]
import random
key ＝ random.randint(1, 20)
i ＝ 0; j ＝ 8; s ＝″″
while i <＝ j：
　 m ＝ (i ＋ j) ∥ 2
　 if a[m] > key：
　 j ＝ m － 1; s ＝ s ＋″L″
　else：
　 i ＝ m ＋ 1; s ＝ s ＋″R″
執行該程序段后，輸出內容可能是(　　)
A.LR B.LLL
C.RLR D.RRRR
答案　D
思維點撥
明考向 根據題意畫出二叉樹如圖所示，當找到key時沒有結束查找，而是繼續向右查找
精　點　撥 A 若查找4，則為LRL，若查找5，則為LRRL
B 查找小于1的數，查找1，則為LLR，產生key的值不可能是1
C 查找8或9的結果是RRL，不可能是RLR
D 當查找大于等于12的數時，結果為RRRR
答案　D
變式 有如下Python程序段：
import random
def binary(L，R，key)：
　　m＝(L＋R)∥2
　　if L>R：
　 return R
　　if key<＝a[m]：
　 return binary(m＋1，R，key)
　　else：
　 return binary(L，m－1，key)
a＝[9，8，7，7，7，5，5，3]
x＝random.randint(1，4)*2＋1
print(binary(0，7，x))
執行該程序段后，輸出結果不可能是(　　)
A.1 B.4 C.6 D.7
答案　A
解析　程序實現查找右極值的索引位置。產生x的范圍是1，3，5，7，9，當找到后還要向右繼續查找，因此屬于查找右極值。
重難點1　二分查找的算法思想
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
答案　A
解析　本題考查二分查找的算法思想。第1次查找的是最中間的節點a4，因此A選項正確。B選項a2比a4小，查找到a6后，不可再去找a2。C選項a5比a4大，也不可能。D選項第3次查找，要么a5或a7，不可能2個數同時被查找到。
2.有如下Python程序段，輸入正整數key值，執行該程序段，輸出的值可能是(　　)
a＝[6，15，18，20，25，30，35，38]
key＝int(input(″輸入要查找的數據：″))
i＝0；j＝len(a)－1
s＝″″
while i<＝j：
　 m＝(i＋j＋1)∥2
　 s＋＝str(a[m])＋″，″
　 if key＝＝a[m]：
　 break
　 if key　 j＝m－1
　 else：
　 i＝m＋1
print(s[：－1])
A.25，20 B.25，18，20
C.25，15，6 D.25，30，35
答案　B
解析　根據題意，圖出對應的二叉樹，可以得到相應的查找路徑。
3.有如下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] < target:
　 left ＝ mid ＋ 1
　　elif nums[mid] > target:
　 right ＝ mid － 1
該程序段運行后，列表lst的長度不可能為(　　)
A.1 B.2 C.3 D.4
答案　D
解析　本題考查二分查找。列表長度就是二分查找的查找次數。列表共8個元素，最少1次，最多4次。查找到76時，不可能繼續往右查找，所以4次是不可能的。
4.有如下Python程序段：
import random
def find(x，y，key)：
　 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，key)
a ＝ [2，4，6，8，10，12，14，16]
key＝random.choice(a)　#從序列的元素中隨機挑選一個元素
print(find(0，len(a)－ 1，key))
上述程序執行完后，函數 find 被調用的最多次數是(　　)
A.3 B.4 C.5 D.6
答案　B
解析　本題考查二分查找、自定義函數的綜合應用。由“key＝random.choice(a)”可知查找鍵key是一定可以找得到的，由題中算法可知，找到最少找1次，最多找int(log2n)＋1次，本題中序列a中共有8個成員，則最多找4次。
5.某二分查找算法的程序段如下：
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
執行該程序段后，下列說法正確的是(　　)
A.該程序若要實現二分查找，要求數組a按降序排列
B.若n為－2，則查找key值可能等于a[3]的值
C.若n為2，則查找 key 的值可能小于a[10]
D.n的值最小為－4，最大為4
答案　C
解析　本題考查二分查找算法。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個。
6.如下 Python 程序段：
import random
a＝[1，3，5，7，9，11，13，15]
key＝random.randint(1，8)*2
i，j＝0，len(a)－1
s＝0
while i<＝j：
　 m＝(i＋j＋1)∥2
　 if a[m]＝＝key：
　 break
　 if a[m]>key：
　　　j＝m－1；s－＝1
　 else：
　 i＝m＋1；s＋＝1
print(s)
上述程序執行完以后，s 的值可能有(　　)
A.4 種 B.5種 C.7種 D.8 種
答案　A
解析　本題考查二分查找。列表a中的元素為1－15中的奇數，查找的key為2－16中的偶數，所以查找的結果不存在a[m]＝＝key也就是找到的情況，break不會被執行。查找的過程如下：s的值可能為－2，－1，1，3，共4種。
重難點2　極值查找
1.某二分查找算法的 Python 程序段如下：
import random
key＝random.randint(1，4)*2
a＝[2，3，4，4，4，6，7，10]
ans＝0；i＝0；j＝len(a)－1
while i<＝j：
　 m＝(i＋j)∥2
　 if key>＝a[m]：
　 i＝m＋1
　 else：
　 j＝m－1
　 ans＋＝a[m]
print(ans)
執行該程序段后，ans 的值不可能是(　　)
A.27 B.14 C.11 D.9
答案　C
解析　查找key值可能是2，4，6，8。當找到key后沒有結束循環，而是查找向右的key，當key＝2時，ans＝4＋3＋2＝9；當key＝4時，ans＝4＋6＋4＝14；當 key＝6 時，ans＝4＋6＋7＝17；當 key＝8時，ans＝4＋6＋7＋10＝27。
2.有如下Python程序段：
a ＝ [15, 20, 32, 32, 54, 66, 94, 96]
f ＝ [0] * len(a)
key ＝ 2 * random.randint(10, 47) ＋ 1
i ＝ 0; j ＝ len(a) － 1; s ＝ 0; n ＝ 0
while i <＝ j：
　　m ＝ (i ＋ j ＋ 1) ∥ 2
　　f[m] ＝ 1
　　if key <＝ a[m]：
　 j ＝ m － 1; n ＝ n － 1
　　else：
　 i ＝ m ＋ 1; n ＝ n ＋ 1
s ＝ sum(f)
執行該程序段后，下列說法正確的是(　　)
A.變量i的值可能為3
B.變量n的值可能為3
C.變量s的值一定為3
D.變量f的值可能為[1，0，1，0，1，0，0，0]
答案　C
解析　程序的功能是查找[21，95]范圍內的奇數key，若找到后還要向左查找。
3.有如下Python程序段：
#隨機產生10個整型元素的非降序序列，依次存入列表a(a[0]！＝a[9])，代碼略
a＝[]
key＝int(input())
i＝0；j＝9
n＝0
while i<＝j:
　　m＝(i＋j)∥2
　　n＋＝1
　　if a[m]　 i＝m＋1
　　else：
　 j＝m－1
執行上述程序段后，下列說法不正確的是(　　)
A.a[i＋1]可能等于key
B.a[j]可能等于key
C.i一定等于j＋1
D.n的值一定大于2
答案　B
解析　本題考查二分查找。當找到key后并沒結束查找，而是向左繼續查找，因此i一定等于j＋1，查找的是最左邊的極值，a[i]可能等于key，則于a[i]和a[i＋1]可能相等，a[i＋1]可能等于key；但a[j]絕對不可能等于key。由于有10個數，畫出對應的二叉樹，有4層，3層為滿二叉樹，因此至少查找3次。
4.如下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　　 ③m
B.①a[m]>key　　②R ＝ m－1　③m
C.①a[m]>＝key　②R ＝ m－1　③R
D.①a[m]>＝key　②R ＝ m　　 ③R
答案　C
解析　在非遞增數組a中查找最后一個大于等于key的元素，即當a[m]和key相等時，也要往后查找，排除選項A和B。當a[m]小于key時，索引位置m上值已經查找過了，因此可以不查找。
重難點1　二分查找的算法思想
1.某二分查找算法的 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
解析　根據算法畫出二叉樹如圖所示，找到后并不結束循環。
2.某二分查找算法的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
數組a中的元素各不相同且按降序排列，執行該程序段后n的值為4，則key的值不可能為(　　)
A.a[1] B.a[4] C.a[12] D.a[16]
答案　D
解析　本題考查二分算法以及二分判定樹。根據本題代碼m＝(i＋j＋1)∥2，畫出二分判定樹，位于二分判定樹第4層的節點下標分別是1、4、7、9、12、14、17、19所以key的值不可能是a[16]。
3.有如下 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
解析　本題考查二分查找以及其變式。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。
4.有如下 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
答案　B
解析　本題考查索引排序和二分查找算法。key值在30－60(60取不到)，在列表a中只有40、59、32符合范圍，對應的索引值為2，4，5。
5.如下 Python 程序段：
#導入模塊并隨機產生8個整型元素的非降序的奇數序列，并依次存入列表a[0]至a[7]，代碼略
key＝random.randint(1，20)
i＝0；j＝7；s＝0
while i<＝j：
　　m＝(i＋j＋1)∥2
　　if a[m]＝＝key：
　 break
　　if a[m]>key：
　 j＝m－1
　 else：
　 i＝m＋1
　s＋＝ 1
執行上述程序段后，下列說法不正確的是(　　)
A.a[j]可能小于a[i]＋2
B.a[i]可能等于key
C.i一定等于j＋1
D.s的值一定小于等于4
答案　C
解析　A選項數組是一個非降序的奇數序列，當找不到的情況下，j小于i，a[j]可能小于 a[i]＋2。C選項若數據能找到，則i小于或等于j。D選項8個數據最多查找4次。
6.有如下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)
執行該程序段后，下列說法正確的是(　　)
A.n的值可能為4
B.若n值為2，則必定滿足i<＝j
C.m的值可能為1
D.若n值為3，則key的值可能是45
答案　B
解析　考查二分查收算法思想。Key是[40，70]區間的偶數，n是循環次數。畫出相應的二叉樹。最多查找3次；a[1]為37，查找的位置不可能是1。若查找2次，說明查找的數是50，中間退出循環，滿足條件i<＝j。
7.某二分查找算法的程序如下：
i ＝ 0; j ＝ 9; c ＝ 0
key ＝ int(input())
while i <＝ j：
　　m ＝ (i ＋ j) ∥ 2
　　if a[m] ＝＝ key：
　 break
　　if a[m] > key：
　 j ＝ m － 1
　　else：
　i ＝ m ＋ 1
　c ＋＝ 1
若a＝[2，13，14，19，23，26，29，31，32，38]，運行該程序段后，c的值為2，則key的值不可能是(　　)
A.19 B.29 C.30 D.32
答案　C
解析　根據列表a的值，畫出如圖所示二叉樹，當向右查找時，c的值增加1，查找29，向右查找2次，若查找30，在查找29的基礎上，再向右查找一次，因此需查找3次。
8.班里共n位同學，學號0至n－1，其中有一位同學未交作業。為了找出未交作業的同學學號，假設已交作業的n－1位同學學號從小到大存放于列表a中，則劃線處代碼是(　　)
L，R＝0，n－2
while L<＝R：
　 m＝(L＋R)∥2
　 if a[m]＝＝m：
　 ①________
　 else：
　 ②________
print(③________)
A.①R＝m－1　②L＝m＋1　③L
B.①R＝m－1　②L＝m＋1　③R
C.①L＝m＋1　②R＝m－1　③L
D.①L＝m＋1　②R＝m－1　③R
答案　C
解析　共有n－2位學生交作業，當條件a[m]＝＝m成立，說明未交作業的學生在后半段，因此移到L，反之向左查找R＝m－1。考慮查找結束的極限情況，L必定指向不符合條件的第一個位置，即所找同學學號。
9.有如下Python程序段：
def find_base(x，y)：
　 left, right ＝ 2, 10
　 while left <＝ right：
　 mid ＝ (left ＋ right) ∥ 2
　 value ＝ calc(mid, y)　#calc函數將mid進制的整數y轉化為十進制數
　 if value ＝＝ x：
　　　 return mid
　 elif value < x：
　　　 left ＝ mid ＋ 1
　 else：
　　　 right ＝ mid － 1
　　return －1
x ＝ int(input()) ; y ＝ int(input())
print(find_base(x，y))
執行該程序段后，依次輸入83和123，程序輸出為(　　)
A.2 B.6 C.8 D.－1
答案　C
解析　本題考查進制轉換與二分查找。函數find_base(x，y)的功能為通過二分查找算法查找十進制數x對應另一進制數y的基數，如果不存在則返回－1。由于123O＝83D，最后能夠找到對應的基數為8。
10.有如下 Python 程序段：
def binSearch(i，j，key)：
　 if i>j：
　 return 0
　 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
答案　B
解析　本題考查遞歸法求二分查找，找到后返回中間位置，沒有找到，累加找過的位置m。用索引位置畫出二叉樹為，沒有一處分支節點和為8。
11.有如下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
答案　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。
12.小明為英文字母A～Z定義了一套全新的二進制編碼規則，代碼如下
s＝[chr(i＋65)for i in range(26)]
dc＝{}
for k in s：
　 i，j＝0，len(s)－1
　 rt＝″0″
　 while i<＝j：
　 m＝(i＋j)∥2
　 if s[m]＝＝k：
　　　 dc[k]＝rt
　　　 break
　 elif s[m]　　　 i＝m＋1
　　　 rt＋＝″1″
　 else：
　　　 j＝m－1
　　　 rt＋＝″0″
inp＝input(″請輸入英文字符串：″).upper()#將輸入的英文字母轉為大寫
for c in inp：
　 print(dc[c], end＝″″)
當程序運行后，輸入“OK”后，其輸出的二進制編碼為(　　)
A.01001 0011 B.01001 000
C.00001 0011 D.01001 00110
答案　A
解析　構建一棵26個節點的升序二叉樹，由于26小于31，因此最多查找4次，用一個4位二進制數存儲訪問的節點(標記為1)。
重難點2　極值查找
1.有如下Python程序段：
from random import randint
k＝randint(0，2)*2
i＝0；j＝6；cnt＝0
while i<＝j：
　　cnt＝cnt＋1
　　m＝(i＋j)∥2
　　if a[m]＝＝a[k]：
　 break
　　if a[m]　 i＝m＋1
　　else：
　 j＝m－1
數組元素 a[0]到 a[6]各不相同且按升序排列，執行該程序段，下列說法不正確的是(　　)
A.m的值不可能為6
B.cnt的值一定為3
C.變量 i、j的值一定相同
D.i的值可能小于m
答案　D
解析　本題考查二分查找的算法思想。查找的k值為0，2，4，即a[0]、a[2]、a[4]中的一個數，畫出判定二叉樹。 由圖可知，查找次數cnt均為3次，m只能是0，2，4。查找的值發生在葉子節點，因此區間中只剩下最后一個數，i，j，m的值是相等的。
2.某二分查找算法的Python程序段如下：
#生成若干數據有序排列后存儲在列表d，代碼略
n＝0
i，j＝0，len(d)－1
while i<＝j：
　　m＝(i＋j)∥2
　　print(d[m]，end＝″ ″)
　　if d[m]＝＝key：
　 break
　　elif d[m]　　　 i＝m＋1
　　else：
　　　 j＝m－1
　　　 n＋＝1
程序運行后，變量n的值為2，輸出的內容可能是(　　)
A.4 7 7 B. 10 4 12
C.7 6 7 D.9 12 15 18
答案　A
解析　本題考查二分查找算法。如果條件d[m]3.有如下 Python 程序段：
a＝[34，35，38，41，41，41，45，45，69，78]
key＝41；n＝0
i＝0；j＝9
while i<＝j：
　　m＝(i＋j)∥2
　　if key　 j＝m－1
　　else：
　 i＝m＋1
該程序段運行結束后，下列說法正確的是(　　)
A.i的值是3 B.j的值是3
C.i的值是6 D.j的值是6
答案　C
解析　本題考查二分查找。當找到key時，沒有結束循環，而是向右繼續查找。最后一個41的索引位置為5，因此找到后，i向后查找，i 的值是6。
4.有如下 Python 程序段：
import random
a ＝ [1，3，4，6，6，6，9，9，11，12]
key ＝ random.randint(2，5) * 2
i，j ＝ 0，9
while i <＝ j：
　 m ＝ (i ＋ j) ∥ 2
　 if key < a[m]：
　 j ＝ m － 1
　 else：
　 i ＝ m ＋ 1
print(j)
執行該程序段后，輸出的結果不可能是(　　)
A.2 B.3 C.5 D.7
答案　B
解析　 本題考查二分查找的算法思想。產生一個[4，10]之間的偶數，當key＝＝a[m]時，沒有終止查找，還是繼續向右查找，直至i>j。若key值為4，j的值為2；若key值為6和8，j的值為5；若key值為10，j的值為7。
5.某二分查找算法的Python程序如下：
#隨機產生包含20個整型元素的升序序列，依次存入數組a，代碼略
i＝0；j＝19；s＝″″
key＝int(input())
while i<＝j：
　　m＝(i＋j)∥2
　　s＋＝str(m)＋″，″
　　if a[m]>key：
　 j＝m－1
　　else：
　 i＝m＋1
執行上述程序并輸入待查找數據，程序執行后，s的值不可能為(　　)
A.″9，4，1，0，″ B.″9，4，1，2，3，″
C.″9，4，6，5，″ D.″9，14，11，10，12，″
答案　 D
解析　分析程序可知，s為二分過程中生成中值m的順序，該順序應是二分找找判定樹中的一部分，四個選項的部分判定樹如下所示。其中D選項中的節點12不應在節點11的左側，因此D選項錯誤。
6.有如下Python程序：
a＝[0，20，23，23，24，24，31，48，49，73，75]
key＝int(input())
c＝0
i，j＝1，10
while i<＝j:
　 m＝(i＋j)∥2
　 if a[m]<＝key:
i＝m＋1
　 else:
j＝m－1
　 c＋＝1
print(c)
若程序運行后，輸出的結果是 3，則輸入的key可能是(　　)
A.20或73 B.24或49
C.23或24 D.23或49
答案　B
解析　本題考查二分查找。查找范圍是[1，10]，當找到key時仍要往右邊查找，當key＝20、24、49時，查找的次數是3，當key＝23、31、73時，查找的次數是4。(共80張PPT)
第二部分　算法與程序設計
專題12　查找算法
1.掌握對分查找核心算法思想，在一個[i，j]區間中，不斷查找中間位置m，并不斷更新查找區間(更新并畫出左右端點)，直到找到或區間不存在；
2.掌握利用退出語句、標志變量和循環條件不成立的結束循環兩種方式；
3.掌握查找區間不存在時，根據查找鍵值來判斷變量i、j、m的關系.
目 錄
CONTENTS
體系構建
01
真題再現
02
考點精練
03
當堂檢測
04
課后練習
05
體系構建
1
在一個區間為[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肯定成立，則該數在序列中不存在。
真題再現
2
(2024年1月浙江省選考)某算法的部分流程圖如圖所示，若n的值為7，key的值為78，數組元素a[0]至a[n－1]依次存放7，12，24，36，55，78，83，執行這部分流程后，輸出c的值為(　　)
解析　本題考查二分查找算法。變量c表示移動左邊界向右查找的次數。查找78的過程為先找到36，向查查找1次，找到78，結束查找。
B
A.0 B.1
C.2 D.3
考點精練
3
重難點1　二分查找的算法思想5
若題目是要查找的數key已知，采用列表法比較快，用表格列出每次查找數組d的區間開始位置i、j和比較數的位置m及值a[m]，模擬對分查找的過程。中間位置m的計算公式為m＝(i＋j)∥2和m＝(i＋j＋1)∥2，當i＋j為奇數時，兩者沒有區別；當i＋j為偶數時，中間位置有兩個，前者是中間偏左，后者是中間偏右。
運行該程序，輸出的結果可能是(　　)
A.[1，1，0，1，0，0，0，0] B.[1，1，1，1，0，0，0，0]
C.[0，0，1，1，0，0，0，0] D.[0，0，0，1，1，0，1，0]
A
思維點撥
明考向 本題考查二分查找算法的程序實現。根據題意，畫出查找的二叉樹如圖所示，當找到某個數字時，數組f中該數字對應索引位置上值賦值為1
精　點　撥 A 分別訪問索引3，1，0
B 分別訪問索引3，2，1，0，但該路徑不存在
C 分別訪問索引3，2，該路徑也不存在
D 分別訪問索引3，4，6，該路徑也不存在
解析　本題考查二分查找的算法思想。根據題目要求，畫出相應的二叉樹，當找到#號時，向左查找，因此不可能找到B。
B
思維點撥
明考向 本題考查二分查找的算法實現
精點撥 由7個字母構成一個搜索二叉樹，如圖所示，遍歷樹中每個節點，若搜索路徑包含字母ch，則cnt的值增加1，查找BAC時包含字母B的節點個數
答案　C
解析　本題考查二分查找。程序的功能是數組a的i索引前找一個數，滿足a[i]*a[m]＝＝n的個數，因此分別是9*4、12*3、18*2。
C
重難點2　極值查找
當一個非降序序列中存在多個連續相等的數據key時，若要查找最左邊key，設置的查找條件為當a[m]＝＝key時，還需移動j為m－1繼續向左查找，當i>j即i＝j＋1時，查找的區間不存在，此時j指向的就是第1個小于等于key的值；若要查找最右邊的key，當查找成功時，還需移動i為m＋1繼續向右查找，此時i指向的就是第1個大于等于key的值。
D
思維點撥
明考向 根據題意畫出二叉樹如圖所示，當找到key時沒有結束查找，而是繼續向右查找
精　點　撥 A 若查找4，則為LRL，若查找5，則為LRRL
B 查找小于1的數，查找1，則為LLR，產生key的值不可能是1
C 查找8或9的結果是RRL，不可能是RLR
D 當查找大于等于12的數時，結果為RRRR
A
解析　程序實現查找右極值的索引位置。產生x的范圍是1，3，5，7，9，當找到后還要向右繼續查找，因此屬于查找右極值。
當堂檢測
4
重難點1　二分查找的算法思想
重難點2　極值查找
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
A
解析　本題考查二分查找的算法思想。第1次查找的是最中間的節點a4，因此A選項正確。B選項a2比a4小，查找到a6后，不可再去找a2。C選項a5比a4大，也不可能。D選項第3次查找，要么a5或a7，不可能2個數同時被查找到。
解析　根據題意，圖出對應的二叉樹，可以得到相應的查找路徑。
答案　B
解析　本題考查二分查找。列表長度就是二分查找的查找次數。列表共8個元素，最少1次，最多4次。查找到76時，不可能繼續往右查找，所以4次是不可能的。
D
解析　本題考查二分查找、自定義函數的綜合應用。由“key＝random.choice(a)”可知查找鍵key是一定可以找得到的，由題中算法可知，找到最少找1次，最多找int(log2n)＋1次，本題中序列a中共有8個成員，則最多找4次。
B
解析　本題考查二分查找算法。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個。
執行該程序段后，下列說法正確的是(　　)
A.該程序若要實現二分查找，要求數組a按降序排列
B.若n為－2，則查找key值可能等于a[3]的值
C.若n為2，則查找 key 的值可能小于a[10]
D.n的值最小為－4，最大為4
C
解析　本題考查二分查找。列表a中的元素為1－15中的奇數，查找的key為2－16中的偶數，所以查找的結果不存在a[m]＝＝key也就是找到的情況，break不會被執行。查找的過程如下：s的值可能為－2，－1，1，3，共4種。
A
解析　查找key值可能是2，4，6，8。當找到key后沒有結束循環，而是查找向右的key，當key＝2時，ans＝4＋3＋2＝9；當key＝4時，ans＝4＋6＋4＝14；當 key＝6 時，ans＝4＋6＋7＝17；當 key＝8時，ans＝4＋6＋7＋10＝27。
執行該程序段后，ans 的值不可能是(　　)
A.27 B.14 C.11 D.9
C
執行該程序段后，下列說法正確的是(　　)
A.變量i的值可能為3
B.變量n的值可能為3
C.變量s的值一定為3
D.變量f的值可能為[1，0，1，0，1，0，0，0]
C
解析　程序的功能是查找[21，95]范圍內的奇數key，若找到后還要向左查找。
執行上述程序段后，下列說法
A.a[i＋1]可能等于key B.a[j]可能等于key
C.i一定等于j＋1 D.n的值一定大于2
B
解析　本題考查二分查找。當找到key后并沒結束查找，而是向左繼續查找，因此i一定等于j＋1，查找的是最左邊的極值，a[i]可能等于key，則于a[i]和a[i＋1]可能相等，a[i＋1]可能等于key；但a[j]絕對不可能等于key。由于有10個數，畫出對應的二叉樹，有4層，3層為滿二叉樹，因此至少查找3次。
C
解析　在非遞增數組a中查找最后一個大于等于key的元素，即當a[m]和key相等時，也要往后查找，排除選項A和B。當a[m]小于key時，索引位置m上值已經查找過了，因此可以不查找。
課后練習
5
重難點1　二分查找的算法思想
重難點2　極值查找
該程序段執行后，顯示的內容可能是(　　)
A.RRRML B.LM
C.LMRL D.LRRM
A
解析　根據算法畫出二叉樹如圖所示，找到后并不結束循環。
數組a中的元素各不相同且按降序排列，執行該程序段后n的值為4，則key的值不可能為(　　)
A.a[1] B.a[4] C.a[12] D.a[16]
D
解析　本題考查二分算法以及二分判定樹。根據本題代碼m＝(i＋j＋1)∥2，畫出二分判定樹，位于二分判定樹第4層的節點下標分別是1、4、7、9、12、14、17、19所以key的值不可能是a[16]。
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
解析　本題考查索引排序和二分查找算法。key值在30－60(60取不到)，在列表a中只有40、59、32符合范圍，對應的索引值為2，4，5。
C
解析　A選項數組是一個非降序的奇數序列，當找不到的情況下，j小于i，a[j]可能小于 a[i]＋2。C選項若數據能找到，則i小于或等于j。D選項8個數據最多查找4次。
執行上述程序段后，下列說法
A.a[j]可能小于a[i]＋2
B.a[i]可能等于key
C.i一定等于j＋1
D.s的值一定小于等于4
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
C
解析　根據列表a的值，畫出如圖所示二叉樹，當向右查找時，c的值增加1，查找29，向右查找2次，若查找30，在查找29的基礎上，再向右查找一次，因此需查找3次。
若a＝[2，13，14，19，23，26，29，31，32，38]，運行該程序段后，c的值為2，則key的值不可能是(　　)
A.19 B.29 C.30 D.32
C
解析　共有n－2位學生交作業，當條件a[m]＝＝m成立，說明未交作業的學生在后半段，因此移到L，反之向左查找R＝m－1。考慮查找結束的極限情況，L必定指向不符合條件的第一個位置，即所找同學學號。
C
解析　本題考查進制轉換與二分查找。函數find_base(x，y)的功能為通過二分查找算法查找十進制數x對應另一進制數y的基數，如果不存在則返回－1。由于123O＝83D，最后能夠找到對應的基數為8。
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
B
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。
解析　構建一棵26個節點的升序二叉樹，由于26小于31，因此最多查找4次，用一個4位二進制數存儲訪問的節點(標記為1)。
A
數組元素 a[0]到 a[6]各不相同且按升序排列，執行該程序段，下列說法
A.m的值不可能為6 B.cnt的值一定為3
C.變量 i、j的值一定相同 D.i的值可能小于m
D
解析　本題考查二分查找的算法思想。查找的k值為0，2，4，即a[0]、a[2]、a[4]中的一個數，畫出判定二叉樹。 由圖可知，查找次數cnt均為3次，m只能是0，2，4。查找的值發生在葉子節點，因此區間中只剩下最后一個數，i，j，m的值是相等的。
程序運行后，變量n的值為2，輸出的內容可能是(　　)
A.4 7 7 B. 10 4 12
C.7 6 7 D.9 12 15 18
A
解析　本題考查二分查找算法。如果條件d[m]該程序段運行結束后，下列說法正確的是(　　)
A.i的值是3 B.j的值是3
C.i的值是6 D.j的值是6
C
解析　本題考查二分查找。當找到key時，沒有結束循環，而是向右繼續查找。最后一個41的索引位置為5，因此找到后，i向后查找，i 的值是6。
執行該程序段后，輸出的結果不可能是(　　)
A.2 B.3 C.5 D.7
B
解析　 本題考查二分查找的算法思想。產生一個[4，10]之間的偶數，當key＝＝a[m]時，沒有終止查找，還是繼續向右查找，直至i>j。若key值為4，j的值為2；若key值為6和8，j的值為5；若key值為10，j的值為7。
執行上述程序并輸入待查找數據，程序執行后，s的值不可能為(　　)
A.″9，4，1，0，″ B.″9，4，1，2，3，″
C.″9，4，6，5，″ D.″9，14，11，10，12，″
D
解析　分析程序可知，s為二分過程中生成中值m的順序，該順序應是二分找找判定樹中的一部分，四個選項的部分判定樹如下所示。其中D選項中的節點12不應在節點11的左側，因此D選項錯誤。
若程序運行后，輸出的結果是 3，則輸入的key可能是(　　)
A.20或73 B.24或49
C.23或24 D.23或49
B
解析　本題考查二分查找。查找范圍是[1，10]，當找到key時仍要往右邊查找，當key＝20、24、49時，查找的次數是3，當key＝23、31、73時，查找的次數是4。

展開更多......

收起↑