資源簡介

(共22張PPT)
5.4 數 據 查 找 （二）
——二 分 查 找
冊 別：選擇性必修1
學 科：高中信息技術（浙教版）
學習目標：
能理解二分查找的算法思想。
能合理選用數據結構，理解二分查找的范圍與條件。
能用自然語言、流程圖、Python語言、二叉樹實現二分查找。
能熟練應用二分查找算法，解決生活、學習中的問題。
閱讀教材P137-141，可根據個性學習暫停或加速播放課程。
猜一猜：
小明的計時手表多少money？
已知前提：價格20-80元？
第1次：50
高了
第2次：40
低了
第3次：45
對了
二分查找概念：
二分查找（binary search）又稱折半查找，對分查找。
它是一種效率很高的查找方法，但被查找的數據序列必須是有序的。
二分查找算法思想
②如果中間位置上的元素內的數值與查找鍵不同，根據數組元素的有序性，就可確定應該在數組的前半部分還是后半部分繼續進行查找
③在新確定的范圍內，繼續按上述方法進行查找，直到獲得最終結果。
①將查找鍵與有序數組內處于中間位置的元素進行比較；
a[0] a[1] a[2] a[3] a[4] a[5] a[6]
1 2 3 4 5 6 7
a[0] a[1] a[2] a[3] a[4] a[5] a[6]
1 2 3 4 5 6 7
a[0] a[1] a[2] 或 a[4] a[5] a[6]
1 2 3 5 6 7
提示：（1） 10個數據存儲在d[0]到d[9] （2）Key=12
i=0
j=9
m=4
i=0
j=3
m=1
d [0]
d [1]
d [2]
d [3]
d [4]
d [5]
d [6]
d [7]
d [8]
d [9]
16
5
21
28
18
26
12
39
56
48
此時i=0，j=3，m=1時，a[m]==key，找到結束查找。
二分查找實踐體驗：
在數組d的10個元素中，已按升序存儲了10個數據：5、12、16、18、21、26、28、39、48、56，如何用二分法查找數據12（已存儲在變量key中）？
思考：
如何確定查找區間中點m的位置？
m=（i+j)//2
m=（i+j+1)//2
討論：
查找范圍（i,j）的變化情況？
將查找鍵key值與d[m]比較，結果必然是如下三種情況之一：
keykey=d[m] 找到了需要的數據。
key>d[m] 數組d遞增，新的查找范圍為【m+1，j】。
思考：若數組d遞減，查找范圍（i,j）如何變化？
keykey>d[m] 數組d遞減，新的查找范圍為【i，m-1】。
二分查找的流程圖描述(升序序列中查找）：填一填
開始
i=0，j=n-1
i<=j
Y
d[m]==key
N
j←m-1
未找到，輸出結果
找到，輸出結果
結束
Y
N
m←i+j /2
d[m]>key
i←m+1
N
Y
（1）
（2）
二分查找規律：
keykey=d[m] 找到了需要的數據。
key>d[m] 與①相同的理由，必須在新的范圍（m+1，j）中繼續查找。
這樣，除了出現情況②，在通過一次比較后，新的查找范圍將不超過上一次查找范圍的一半。
查找鍵key值與d[m]比較結果情況總結：
中點位置 m=（i+j)/2
二分查找Python程序實現:
d=[6,12,15,18,22,25,28,35,46,58]
key=int(input(“輸入待查找元素：”)）
f=False
i = 0 # i和j定義子數組的邊界，一開始搜索的是整個數組
j = len(d)-1
while i <= j:
m = (i+j) //2
if d[m] == key:
f=True
b=m
break
if key < d[m]: # 到左邊去找
j = m-1
else: # 到右邊去找
i = m + 1
if f==True:
print("查找成功！第"+str(b)+"個")
else:
print("沒有找到！")
二分查找的遞歸實現:
def bsearch(k,dat,i,j):
if i>=j+1: # 遞歸結束條件1
print("未找到！") # 遞歸結束值1
return
m = (i+j) //2
if dat[m] == k: # 遞歸結束條件2
print("找到了！第"+str(m+1)+"個" ) # 遞歸結束值2
return
elif k < dat[m]: # 到左邊區間去找
return bsearch(k,dat,i,m-1) # 遞歸表達式，自己調用自己
elif k >= dat[m]: # 到右邊區間去找
return bsearch(k,dat,m+1,j) # 遞歸表達式，自己調用自己
#主程序
d=[6,12,15,18,22,25,28,35,46,58]
print(d)
key=int(input("輸入待查找元素："))
i=0;j=len(d)-1
bsearch(key,d,i,j)#調用bsearch函數
順序查找、二分查找對比
順序查找 二分查找
查找對象 無要求 只可查找有序的序列
效率 低 高
最少查找次數 1 1
最多查找次數 <=n <=int(log2n)+1
平均查找次數
≈ log(n+1)-1
二分查找判定樹：二叉樹
i=0
j=9
m=4
i=0
j=3
m=1
d [0]
d [1]
d [2]
d [3]
d [4]
d [5]
d [6]
d [7]
d [8]
d [9]
16
5
21
28
18
26
12
39
56
48
i=5
j=9
m=7
4
i=0
j=0
m=0
i=2
m=2
j=3
i=3
j=3
m=3
1
7
0
2
5
8
3
6
9
二分查找判定樹：二叉樹
d [0]
d [1]
d [2]
d [3]
d [4]
d [5]
d [6]
d [7]
d [8]
d [9]
16
5
21
28
18
26
12
39
56
48
4
1
7
0
2
5
8
3
6
9
21
12
39
5
16
26
48
18
28
56
二分查找判定樹：二叉排序樹
找12：從根結點到待查結點的一條路徑為21→12，比較次數為2次完成。
21
12
39
5
16
26
48
18
28
56
找18： 21→12→16→18，由此可知，在n個元素排序的順序表里，某一次查找過程中，所做比較次數不超過判定樹的高度加1，即 log2n +1,即 <=int(log2n)+1
生活實戰應用：
某校期中考試部分學生信息技術與通用技術成績如右表所示，查詢某賦分數的所有學生名單，并輸出共有幾個同分數的學生，要求實現以上功能，如查詢不到則顯示“無此分數的學生”。請編程實現。
生活實戰應用：
#讀取csv中的文件數據
import csv #導入csv模塊
f=open("期中考技術成績.csv",'r')#打開csv數據文件
c=[]#定義空列表a
r=csv.reader(f)#建立一個讀入數據的對象r
n=0#記錄數初值
for i in r:#每一行為c列表一個元素,此元素為字符串
c.append(i)#從表中第一行開始依次讀入到c列表中
n+=1 #記錄數增加1
f.close#關閉csv數據文件
print("從CSV中獲得的數據：")
for i in range(len(c)):
print(c[i]) #輸出csv文件中讀入的記錄
key=int(input("請輸入要查找的分數："))
i=1;j=len(c)-1#查找范圍索引值的左右端點值
while i<=j: #左端點i<=右端點j,繼續二分查找
m=(i+j)//2 #計算中點索引值
if keyi=m+1 #在表的右區間找
else: #key>=int(c[m][2])時
j=m-1 #在表的左區間找
print("要查找的"+str(key)+"數據第一個位置是："+str(i))
b=i #記錄第一個位置到b中
#找第一個key所在的位置結束
#找最后一個key所在的位置
i=1;j=len(c)-1#查找范圍索引值的初值與終值
while i<=j:#左端點i<=右端點j,繼續二分查找
m=(i+j)//2#計算中點索引值
if key<=int(c[m][2]):#表數據降序，
i=m+1#在表的右區間找
else:#key>int(c[m][2])時
j=m-1#在表的左區間找
print("要查找的"+str(key)+"數據最后一個位置是："+str(j))
print("總共",key,"的個數為",j-b+1,"個")
print(c[0])
for k in range(b,j+1): #輸出所有key的人員信息
print(c[k])
課堂小結
二分查找
算法思想 算法描述 與順序查找的對比
查找區間i,j,m的位置
個數、不大于、不小于問題
程序實現
查找鍵key值與d[m]比較
學習評價
對自己的表現進行客觀的評價，并思考后續完善的方向。（3=優秀，2=一般，1=仍需加油）
評分項 自我評價
能理解二分查找算法的特點及適用范圍 3 2 1
能確定查找區間i,j及中點m的位置 3 2 1
能自主學習教材并用自然語言、流程圖描述順序查找算法 3 2 1
能夠用Python語言描述順序查找算法 3 2 1
能理解查找鍵key值與d[m]比較的三種情況 3 2 1
能夠理解二分查找的判定樹 3 2 1
能夠查找相同元素個數、不小于某元素位置或小于某元素位置等實際應用 3 2 1
課后作業
1.某對分查找算法的 VB 程序如下：
i = 0;j = 29
m = (i + j) // 2
while i <= j and key!=a[m]:
If key > a[m]:
i = m + 1
else:
j = m – 1
m = (i+j)// 2 # ①
數組元素 a[0]到 a[29]各不相同且按升序排列，若查找鍵key與a[8]相等，執行該程序段，①處語句的執行次數是
A.2 B.3 C. 4 D.5
B
課后作業
2.某校校友錄登記表students_sorted.csv如右圖所示，已知校友錄已經按照姓名的拼音升序排序，為了快速查找某位校友，輸入校友名稱，輸出該名字的所有校友信息，若輸入的校友不在校友錄登記表中，則輸出“查無此人”如下圖所示：
程序代碼如下，請在劃線處填寫合適的代碼語句：
import csv
#讀取csv文件
with open("stu.csv", "r", encoding='gb18030') as f:
data = []
reader = csv.DictReader(f)
for row in reader:
data.append(row)
stuname = input("請輸入要查找的姓名：\n")
n = len(data)
L = 0
R = n-1
while ① :
mid = (L + R) // 2
if data[mid]["stu_name"]>=stuname:
R = mid-1
elif data[mid]["stu_name"]L = mid+1
if data[L]["stu_name"] == stuname:
②
while data[start]["stu_name"] == stuname:
print( ③ )
if start==n:
break
start += 1
else:
print("查無此人")
2.①L<= R ②start = L ③data[start

展開更多......

收起↑