《二分查找算法實現》教學設計

任宏梅

教材分析

“二分法查找算法實現”選自教育科學出版社選修部分內容，為高中《算法與程序設計》第三章第三節。青少年學習編程是對個人學習能力和創造思維力的培養，不斷提升他們發現和解決問題的能力。本節課內容在第三章屬于后部，是在對教材前面所講的兩大內容已經掌握的基礎上的后續學習。學生已經掌握了第三章的數組理解和應用，知道了數組中指針的變化、數組存儲值變化；掌握了教材第二章程序的基本結構、循環結構的應用。在已經學習這兩個知識點的基礎上，繼續學習二分法高效查找。

學情分析

實施對象是高中一年級學生，這些學生沒有編程的基礎，之前也幾乎沒有選修編程。因此，他們不知道數組是什么、數組怎么用，也不懂什么循環結構。如果按常規學習方法，直接給他們用專業的術語授課，學生會如聽天書，收效甚微。教師應選擇從生活的應用中來的設計，引導學生理解過程和方法，在此基礎上自主建構二分法的算法。

教學目標

知識與技能目標：理解二分法查找算法，體驗二分法查找的實現。

過程與方法目標：生活應用“找繩子”活動中創設情境，通過學生討論，聯系生活實際，形成二分查找是高效查找的感官認識。通過任務的驅動、三個指針變化的小動畫呈現步驟等形式，讓學生理解二分查找的算法。實踐二分法“猜數”的計算機小程序，體驗二分算法的實現。

情感態度與價值觀目標：在生活應用的教學中，培養學生的信息技術素養。通過任務驅動、動畫呈現的問題解決式教學，提升學生理解問題、歸納總結的能力。

教學重點、難點

重點：分析二分法查找的過程。

難點：二分法查找算法的實現。

教學過程

環節一：創設情境，生活導入

教師讓學生完成一個活動。這是一個柜子a，有12個抽屜，每個抽屜中放一根紅色的繩子。其中有一根與老師手中的黑色繩子等長。請問：①如何找到等長的繩子？找的次數？②如果按照從短到長的順序放入這12根繩子，如何找？③如果是成千上萬甚至上億的數據要找一個目標值，你會選擇哪種方法？引導學生進入課堂預設的學習目標，得出二分查找的概念。

設計意圖：生活應用導入。學生回答問題一的方法：順序比較每個抽屜里的繩子，找到的最多次數是11?；卮饐栴}二的方法：先從中間抽屜的繩子做比較，然后向兩邊比較，找到的最多次數少于11?；卮饐栴}三的方法：選擇第二種方法查找。學生很快地進入課堂預設的學習目標，引出二分查找的概念。同時教師強調，采用第二種方法的前提是數據必須是有序排列。

教師提問：因為12個抽屜一模一樣，那如何記錄目標繩子所在的位置？

學生思考后回答：給抽屜編號，來標記存放的位置。

設計意圖：考慮到學生是零編程基礎，不懂“數組”的概念和應用，故設計“編號”來表示存放的位置。

師生互動，教師演示在柜子a（有序排列）中找到目標繩子的過程。根據該活動，學生討論5個問題，得出三條重要語句：mid=（low+high）/2（向下取整）；low=mid+1；high=mid-1。

教師準備三張分別寫著low、high、mid的標簽紙。low代表查找范圍的開始位置，夾在第1個抽屜的位置；high代表查找范圍的結束位置，夾在第12個抽屜的位置；mid代表查找范圍的中間位置，夾在第6個抽屜的位置（請學生回答mid值，此處約定“向下取整”）。演示在有序排列的柜子a中找到目標繩子的過程。強調突出在查找過程中，隨著查找范圍的變化，low、high、mid標簽的位置變化。

學生思考并討論：①關鍵位置有幾個？（3個：low、high、mid）②如何找到目標繩子？（重復比較“目標值=mid所指值”嗎？）③重復的條件是什么？（low<=high暫未找到目標值的情況下）④如果low>high，說明什么問題？（找不到）

設計意圖：用標簽紙low、high、mid代表三個指針，指針代表的是數據存放的位置，把抽象的問題形象化呈現。第1次找目標繩子時，low=1，high=12，mid=6，取第6個抽屜里的紅繩子，與教師手中的黑繩子比較，紅繩子短于黑繩子。接下來，查找的范圍發生變化，查找的開始位置low變為mid+1，查找的結束位置high保持不變，mid值取新的（low+high）/2（向下取整），繼續比較，直到找到目標繩子。該活動得到三條重要的語句：mid=（low+high）/2（向下取整），low=mid+1，high=mid-1。

教師引導提問，如果從成千上萬的數據中去找一個目標值，大家會采用“人工加工”方式找，還是采用“計算機加工”方式找？

學生思考并回答，采用“計算機加工”方式找。

設計意圖：當我們用“計算機的存儲空間”代替“抽屜”，用具體的“數值”代替實物“繩子”時，我們就可以讓計算機來找目標值了。當然，也需要給計算機的存儲空間編號，來標記存儲位置。課堂教學進入例題的講解分析。

環節二：深入具體，講授新課

師生分析兩個例題。

例1：在如圖1所示的有序數列中，查找值為46的記錄的過程。如圖2、圖3所示。

設計意圖：“小動畫”形象地呈現查找的過程。每一次查找，記錄三個指針的變化情況。師生共同分析，表格填空，完成具體指針的值。

例2：在如下頁圖4所示的有序數列中，寫出查找值為22的記錄的過程。（模仿例1，寫出查找的過程）

設計意圖：采用任務驅動的方法，邊學邊做，分析本課的學習重點。讓學生學會遷移運用。“希沃授課助手”拍照上傳，實時呈現學生例2作業完成情況并點評，強調當low>high時，找不到。

環節三：總結歸納，構建算法

師生歸納得出二分查找的算法描述。

步驟①：設三個指針low、high、mid表示查找區間的下界、上界和中間位置。

步驟②：判斷low<=high？

若成立：mid=（low+high）/2取整；

如果X=mid所指值，找到，查找結束；

如果X>mid所指值，low=mid+1，重復步驟②；

如果X

若不成立：找不到，查找結束。

設計意圖：通過以上兩個例子，幫助學生梳理二分查找的算法，建構自己的知識體系。

例3：設有50個數據元素的有序數列，采用二分查找，最大查找次數為多少（如圖5）？

設計意圖：師生共同分析數據變化的過程，找出一般規律。從具體到抽象的認知方式，深刻理解二分查找的“折半”思想。

環節四：反饋評價，查漏補缺

學生獨立完成練習：

（1）設有100個有序排列的數據元素，采用二分查找，最大查找次數為（ B ）。

A.6 B.7

C.8 D.10

（2）用自然語言描述二分查找的算法。

步驟①：設三個指針。low表示查找區間第________個數的位置，high表示查找區間第________個數的位置，mid表示查找區間第________個數的位置。

步驟②：判斷low_______high？

若成立：_____________（計算mid的值）；

如果目標值（X）=mid所指值，________________；

如果目標值（X）>mid所指值，_____________，重復步驟②；

如果目標值（X）

若不成立：_________________。

（3）實踐練習：完善代碼（用代碼替換***），體驗二分法猜數的小程序（如下頁圖6）。

設計意圖：練習（1），請學生回答。練習（2），通過“希沃授課助手”，實時拍學生的練習到屏幕并點評。鞏固二分法查找的算法。

活動過渡：大家紙上練習做得都很好。但我們知道，“紙上得來終覺淺，絕知此事要躬行”。和學生共同觀察二分法計算機小程序，體驗二分算法的實現。

環節五：總結提高，拓展深化

教師引導學生總結歸納本節課內容，思考出本節課重點內容。

（1）二分查找的數據特征？（有序 無序）

（2）二分查找的算法描述？

（3）與順序查找相比，二分查找的優勢？

（4）達成基礎后，再引導學生思考，進行拓展深化。

（5）思考：二分查找（有序數列長度n）的最大查找次數是多少？（Log2（n）+1）

（6）關注二分法在生活中的應用：二分法求方程的解、電力故障排除等。

設計意圖：教師引導學生回顧，對二分法查找的數據特征以及優勢進行深入總結。共同總結本節課的學習內容，并引導學生關注實際應用。

教學反思

因為學生沒有學習過編程，沒有一點編程的基礎，所以他們不知道數組是什么，怎么用，也不懂什么循環結構。如果按常規，直接給他們用專業的術語授課，學生會如聽天書，沒有收效，所以設計“從柜子的抽屜中找繩子”的活動。將抽屜排上編號，模擬數組的存取，通過找繩子的過程，來體驗三個指針的變化。從生活中來，到生活中去，讓學生從生活中學習。

在例題的選取上，難度梯度上升。例1師生共同分析，例2學生模仿完成，然后師生歸納二分法的算法步驟，例3在學生理解二分法的基礎上來應用，從折半的角度思考問題，突出二分法查找的高效。課堂練習環節，用三個練習來鞏固所學知識，通過“希沃授課助手”，對學生作業進行評價。第三個練習補全代碼，體驗“猜數”小程序，讓學生知道二分法是可以用程序實現的。通過練習反饋和評價，能夠讓學生構建二分法查找的算法，培養計算思維及核心素養。課后提升環節，題有一定難度，希望學生能在掌握、理解二分法算法的基礎上，學會應用思考，從而能歸納得出二分法查找的最大查找次數log2（n）+1。具有挑戰性的內容，對于學有余力的學生可以更好地激發他們的學習興趣，促進他們自主學習。

當然，在學習過程中也遇到了一些問題，例如，一些細節處理依然不到位，對學生的評價還有些欠缺，缺少感染力，沒有完全激發學生的興趣，在教學中仍然是希望按自己的思路進行課堂教學。因此，在后面的教學中，更要注重以生為本，分層次教學，讓學生的思維火花能夠被真正點燃！

點 評

《二分查找算法實現》一課是編程思想中的基礎算法，具備抽象性，思維步驟性很強，教師讓學生形成自己的方法和步驟，搭建自己的認知框架，讓學生真正參與到教學中來很關鍵。本節課教師以學生已經具備的生活技能為切入口，運用已有的認知經驗來解決問題。設計“找繩子”的生活活動引入，在課堂中采用學生討論、任務驅動、小動畫呈現等方式，吸引學生主動參與課堂的學習。教師以談話式教學娓娓道來，讓學生對二分查找算法有了實際的體驗，化抽象為具體，知道適用的場合，是值得借鑒和學習的。教師在整個教學過程中，以完成一個個具體的任務為線索，把教學內容巧妙地隱含于學習任務中。學生在教師的循循善誘下，通過一個個小任務達成了學習目標。通過自主探究和小組合作學習，調動了學生的積極性，提高了學生的信息素養。從生活到學習，從學習到生活，教師根植教材，不拘泥于教材，讓學生感受到信息技術的巨大魅力。學習中每個學生都能獨立思考，認真探索，但深層次合作交流稍微欠缺?？傮w來說，該節課設計結構完整，亮點突出，確實是一節值得我們學習和借鑒的好課。