《二分查找算法實(shí)現(xiàn)》教學(xué)設(shè)計(jì)

任宏梅

教材分析

“二分法查找算法實(shí)現(xiàn)”選自教育科學(xué)出版社選修部分內(nèi)容，為高中《算法與程序設(shè)計(jì)》第三章第三節(jié)。青少年學(xué)習(xí)編程是對個人學(xué)習(xí)能力和創(chuàng)造思維力的培養(yǎng)，不斷提升他們發(fā)現(xiàn)和解決問題的能力。本節(jié)課內(nèi)容在第三章屬于后部，是在對教材前面所講的兩大內(nèi)容已經(jīng)掌握的基礎(chǔ)上的后續(xù)學(xué)習(xí)。學(xué)生已經(jīng)掌握了第三章的數(shù)組理解和應(yīng)用，知道了數(shù)組中指針的變化、數(shù)組存儲值變化；掌握了教材第二章程序的基本結(jié)構(gòu)、循環(huán)結(jié)構(gòu)的應(yīng)用。在已經(jīng)學(xué)習(xí)這兩個知識點(diǎn)的基礎(chǔ)上，繼續(xù)學(xué)習(xí)二分法高效查找。

學(xué)情分析

實(shí)施對象是高中一年級學(xué)生，這些學(xué)生沒有編程的基礎(chǔ)，之前也幾乎沒有選修編程。因此，他們不知道數(shù)組是什么、數(shù)組怎么用，也不懂什么循環(huán)結(jié)構(gòu)。如果按常規(guī)學(xué)習(xí)方法，直接給他們用專業(yè)的術(shù)語授課，學(xué)生會如聽天書，收效甚微。教師應(yīng)選擇從生活的應(yīng)用中來的設(shè)計(jì)，引導(dǎo)學(xué)生理解過程和方法，在此基礎(chǔ)上自主建構(gòu)二分法的算法。

教學(xué)目標(biāo)

知識與技能目標(biāo)：理解二分法查找算法，體驗(yàn)二分法查找的實(shí)現(xiàn)。

過程與方法目標(biāo)：生活應(yīng)用“找繩子”活動中創(chuàng)設(shè)情境，通過學(xué)生討論，聯(lián)系生活實(shí)際，形成二分查找是高效查找的感官認(rèn)識。通過任務(wù)的驅(qū)動、三個指針變化的小動畫呈現(xiàn)步驟等形式，讓學(xué)生理解二分查找的算法。實(shí)踐二分法“猜數(shù)”的計(jì)算機(jī)小程序，體驗(yàn)二分算法的實(shí)現(xiàn)。

情感態(tài)度與價(jià)值觀目標(biāo)：在生活應(yīng)用的教學(xué)中，培養(yǎng)學(xué)生的信息技術(shù)素養(yǎng)。通過任務(wù)驅(qū)動、動畫呈現(xiàn)的問題解決式教學(xué)，提升學(xué)生理解問題、歸納總結(jié)的能力。

教學(xué)重點(diǎn)、難點(diǎn)

重點(diǎn)：分析二分法查找的過程。

難點(diǎn)：二分法查找算法的實(shí)現(xiàn)。

教學(xué)過程

環(huán)節(jié)一：創(chuàng)設(shè)情境，生活導(dǎo)入

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

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

教師提問：因?yàn)?2個抽屜一模一樣，那如何記錄目標(biāo)繩子所在的位置？

學(xué)生思考后回答：給抽屜編號，來標(biāo)記存放的位置。

設(shè)計(jì)意圖：考慮到學(xué)生是零編程基礎(chǔ)，不懂“數(shù)組”的概念和應(yīng)用，故設(shè)計(jì)“編號”來表示存放的位置。

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

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

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

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

教師引導(dǎo)提問，如果從成千上萬的數(shù)據(jù)中去找一個目標(biāo)值，大家會采用“人工加工”方式找，還是采用“計(jì)算機(jī)加工”方式找？

學(xué)生思考并回答，采用“計(jì)算機(jī)加工”方式找。

設(shè)計(jì)意圖：當(dāng)我們用“計(jì)算機(jī)的存儲空間”代替“抽屜”，用具體的“數(shù)值”代替實(shí)物“繩子”時(shí)，我們就可以讓計(jì)算機(jī)來找目標(biāo)值了。當(dāng)然，也需要給計(jì)算機(jī)的存儲空間編號，來標(biāo)記存儲位置。課堂教學(xué)進(jìn)入例題的講解分析。

環(huán)節(jié)二：深入具體，講授新課

師生分析兩個例題。

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

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

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

設(shè)計(jì)意圖：采用任務(wù)驅(qū)動的方法，邊學(xué)邊做，分析本課的學(xué)習(xí)重點(diǎn)。讓學(xué)生學(xué)會遷移運(yùn)用?！跋Ｎ质谡n助手”拍照上傳，實(shí)時(shí)呈現(xiàn)學(xué)生例2作業(yè)完成情況并點(diǎn)評，強(qiáng)調(diào)當(dāng)low>high時(shí)，找不到。

環(huán)節(jié)三：總結(jié)歸納，構(gòu)建算法

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

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

步驟②：判斷l(xiāng)ow<=high？

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

如果X=mid所指值，找到，查找結(jié)束；

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

如果X

若不成立：找不到，查找結(jié)束。

設(shè)計(jì)意圖：通過以上兩個例子，幫助學(xué)生梳理二分查找的算法，建構(gòu)自己的知識體系。

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

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

環(huán)節(jié)四：反饋評價(jià)，查漏補(bǔ)缺

學(xué)生獨(dú)立完成練習(xí)：

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

A.6 B.7

C.8 D.10

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

步驟①：設(shè)三個指針。low表示查找區(qū)間第________個數(shù)的位置，high表示查找區(qū)間第________個數(shù)的位置，mid表示查找區(qū)間第________個數(shù)的位置。

步驟②：判斷l(xiāng)ow_______high？

若成立：_____________（計(jì)算mid的值）；

如果目標(biāo)值（X）=mid所指值，________________；

如果目標(biāo)值（X）>mid所指值，_____________，重復(fù)步驟②；

如果目標(biāo)值（X）

若不成立：_________________。

（3）實(shí)踐練習(xí)：完善代碼（用代碼替換***），體驗(yàn)二分法猜數(shù)的小程序（如下頁圖6）。

設(shè)計(jì)意圖：練習(xí)（1），請學(xué)生回答。練習(xí)（2），通過“希沃授課助手”，實(shí)時(shí)拍學(xué)生的練習(xí)到屏幕并點(diǎn)評。鞏固二分法查找的算法。

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

環(huán)節(jié)五：總結(jié)提高，拓展深化

教師引導(dǎo)學(xué)生總結(jié)歸納本節(jié)課內(nèi)容，思考出本節(jié)課重點(diǎn)內(nèi)容。

（1）二分查找的數(shù)據(jù)特征？（有序 無序）

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

（3）與順序查找相比，二分查找的優(yōu)勢？

（4）達(dá)成基礎(chǔ)后，再引導(dǎo)學(xué)生思考，進(jìn)行拓展深化。

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

（6）關(guān)注二分法在生活中的應(yīng)用：二分法求方程的解、電力故障排除等。

設(shè)計(jì)意圖：教師引導(dǎo)學(xué)生回顧，對二分法查找的數(shù)據(jù)特征以及優(yōu)勢進(jìn)行深入總結(jié)。共同總結(jié)本節(jié)課的學(xué)習(xí)內(nèi)容，并引導(dǎo)學(xué)生關(guān)注實(shí)際應(yīng)用。

教學(xué)反思

因?yàn)閷W(xué)生沒有學(xué)習(xí)過編程，沒有一點(diǎn)編程的基礎(chǔ)，所以他們不知道數(shù)組是什么，怎么用，也不懂什么循環(huán)結(jié)構(gòu)。如果按常規(guī)，直接給他們用專業(yè)的術(shù)語授課，學(xué)生會如聽天書，沒有收效，所以設(shè)計(jì)“從柜子的抽屜中找繩子”的活動。將抽屜排上編號，模擬數(shù)組的存取，通過找繩子的過程，來體驗(yàn)三個指針的變化。從生活中來，到生活中去，讓學(xué)生從生活中學(xué)習(xí)。

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

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

點(diǎn) 評

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