資源簡介

教學設計
課程基本信息
課題 5.4 數 據 查 找 （二）——二 分 查 找
教學目標
1.通過猜價格，能理解二分查找的算法思想。 2.通過查詢VIP號， 能合理選用數據結構，理解二分查找的范圍與條件。 3.能熟練應用自然語言、流程圖、Python語言、二叉樹實現二分查找。 4.能熟練應用二分查找算法，解決生活、學習中的問題。
指向的核心素養
●信息意識：學生能夠結合實例，自覺、主動地有意識地選擇恰當的數據結構表達數據比較與處理信息。 ●計算思維：學生能夠結合實例，抽象問題的基本特征，設計算法與數據結構，編程解決問題。 ●數字化學習與創新：要使學生較為熟練地運用二分查找解決生活中的真實問題，并在此過程中自主或協作探究；能夠評估常見的數字化資源與工具對學習數據結構的價值，根據需要合理選擇。 ●信息社會責任：自覺遵守相應的倫理道德和法律法規。
教學內容
教學重點： 1. 二分查找的算法思想。
2. 能熟練應用自然語言、流程圖、Python語言、二叉樹實現二分查找。
教學難點： 能熟練應用二分查找算法，解決生活、學習中的問題。
教學過程
情景引入 猜一猜：小明的計時手表多少money？ 已知前提：價格20-80元？ 二分查找概念： 二分查找（binary search）又稱折半查找，對分查找。 它是一種效率很高的查找方法，但被查找的數據序列必須是有序的。 三、二分查找算法思想：
①將查找鍵與有序數組內處于中間位置的元素進行比較； ②如果中間位置上的元素內的數值與查找鍵不同，根據數組元素的有序性，就可確定應該在數組的前半部分還是后半部分繼續進行查找 ③在新確定的范圍內，繼續按上述方法進行查找，直到獲得最終結果。
四、二分查找實踐體驗：
五、用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、中點位置繪制 2、中點值繪制 九、生活實戰應用：某校期中考試部分學生信息技術與通用技術成績如右表所示，查詢某賦分數的所有學生名單，并輸出共有幾個同分數的學生，要求實現以上功能，如查詢不到則顯示“無此分數的學生”。請編程實現。

展開更多......

收起↑