2023學(xué)年完整公開課版二分法

大江飛虹——二分法查找算法實現(xiàn)海門實驗學(xué)校徐楊峰南通人才計劃找一找場景一：大橋鐵路沿線電路發(fā)生故障，需要搶修!大橋鐵路全線共有277段，編號為1到277，其中有1段發(fā)生故障。我們可以檢測若干電線架的通電情況來排查故障。請各小組成員思考一下，按怎樣的次序進行檢測，能快速找出故障段。試一試，說一說

在軟件中進行模擬，確定最佳方案。

運行桌面學(xué)生文件夾中“檢測”程序。（完成后，在導(dǎo)學(xué)案上寫下故障段的編號和查找所用的次數(shù)，并且進行自我評價）順口溜：找一半

按照順序找一半，一比較，舍一半。繼續(xù)找一半，一半又一半，快速找答案！做一做

場景二：工作人員采用剛才最高效的查找方法把故障找到了，經(jīng)檢測發(fā)現(xiàn)一塊電路板上1個22k阻值的電阻壞了?，F(xiàn)在我們身邊只有一只萬用表和130個備用電阻。（這些電阻已經(jīng)按阻值從小到大有序排列）。

請各小組根據(jù)以上情況，用最高效的方法找到22K阻值的備用電阻,先請在導(dǎo)學(xué)案上寫下解決問題的方法與步驟。這種情況下很顯然用隨機、順序查找法效率比較低。用自然語言描述解決問題的方法與步驟。說一說第1步：

第2步：……說一說第1步：將電阻按順序進行______.第2步：確定查找目標(biāo)電阻的阻值。第3步：（重新）確定電阻查找范圍的起點和終點。第4步：檢測

的阻值并與

。第5步：如果

，

那么

。

第6步：如果

，

那么

。

第7步：如果

，

那么

。……第n步：結(jié)束

編號說明：類似建立電阻數(shù)組中間位目標(biāo)電阻值比較中間位電阻值與目標(biāo)電阻值相等返回目標(biāo)電阻值的位號中間位電阻值大于目標(biāo)電阻值排除高于中間位阻值的電阻，轉(zhuǎn)第三步中間位電阻值小于目標(biāo)電阻值排除低于中間位阻值的電阻，轉(zhuǎn)第三步請各小組根據(jù)方案查找目標(biāo)電阻，并且記錄查找的過程。小組合作完成后，相鄰小組互相復(fù)查一下，并給對方評價。流程圖的描述開始123465下界>上界否否是是找到目標(biāo)，返回位號結(jié)束沒找到否排序編號，形成電阻數(shù)組確定查找目標(biāo)阻值keyA.確定初始查找的范圍B.確定中間位編號C.中間位電阻值是否為目標(biāo)阻值D.中間位電阻值大于目標(biāo)阻值E.新上界=中間位—1F.新下界=中間位+1

在數(shù)學(xué)中可以用二分法來求方程的近似解。算法與程序設(shè)計中主要通過二分法查找數(shù)據(jù)：主要思想是:設(shè)置查找的數(shù)組A[low,up](1)確定該查找范圍的中間位置mid(2)將查找的值key與A[mid]比較。若相等，查找成功返回此位置;否則確定新的查找區(qū)域，繼續(xù)二分查找。得出結(jié)論

如果這些電阻是無序排列的，還能用二分法來查找嗎？為什么？想一想不能。因為即使通過中位值判斷，也無法排除一半的數(shù)據(jù)，無法快速縮小查詢范圍。

二分法查找的前提條件是被查數(shù)據(jù)是有序的。

無序數(shù)據(jù)可以采用順序查找法來查找。場景三：南通貨物行天下你的想象，將是新的方向！大量包裹工人少任務(wù)繁重想一想面臨貨物多，工人少，搬運難的問題，如何來解決？我們先來看一看京東的搬運機器人是怎么工作的？用你的遠(yuǎn)見，開啟你的遠(yuǎn)航！

智能化、自動化的火車站物流中心可以大大提高貨物轉(zhuǎn)運效率。而機器人的運作需要我們事先編寫大量程序，告訴機器人怎么去做。機器人在去倉庫搬運貨物之前，首先需要判斷貨物是否在倉庫里！機器人可以通過在倉庫物流數(shù)據(jù)中查找目標(biāo)貨物單號來進行判斷。(貨物單號通常用入庫時間來編排)那機器人如何快速查找貨物單號呢？

請各小組利用二分法查找算法解決問題，用自然語言進行描述并完成導(dǎo)學(xué)單中的流程圖，參照課本P55。展示流程圖答案開始向A()數(shù)組中讀入N個順序貨單號Key中輸入待查貨單號Low=0,up=n-1A(mid)=keyA(mid)>keyLow>up否否是是找到目標(biāo)結(jié)束沒找到Mid=(low+up)/2Low=mid+1Up=mid—1否說明：low為數(shù)組的下界，up為數(shù)組的上界，mid為中間位課堂拓展嘗試用VB打開工程文件，編寫代碼并調(diào)試運行。滬通長江大橋課堂總結(jié)本節(jié)課學(xué)習(xí)了哪些主要內(nèi)容？

二分法查找的基本思想和二分法查找算法的實現(xiàn)。

如果查找的數(shù)據(jù)較多或需要頻繁進行查找，順序查找效率會比較低，而使用二分法查找則可以提高查找的效率。而二分法查找的數(shù)據(jù)一定要是有序的。

怎樣讓一組無序的數(shù)據(jù)變成有序，便于我們通過二分法進行查找呢，下節(jié)課我們將一起來探討這一問題。知識拓展1）、零基礎(chǔ)入門學(xué)習(xí)VB視頻教程50