1、.折半查找算法及程序實現一、教材分析教學重點：以圖示法方式，演示折半查找算法的基本思想。教學難點：由折半查找算法的思想到程序代碼編寫的轉換，尤其是其中關鍵性語句的編寫是教學中的難點。二、學情分析學生應該已經掌握程序設計的基本思想，掌握賦值語句、選擇語句、循環語句的基本用法和VB基本操作，這節課學生可能會遇到的最大問題是：如何歸納總結對分查找解決不同情況問題的一般規律，鑒于此，在教學中要積極引導學生采取分解動作、比較遷移等學習策略。三、教學目標知識與技能：理解對分查找的概念和特點，通過分步解析獲取對分查找的解題結構，初步掌握對分查找算法的程序實現。過程與方法：通過分析多種不同的可能情況，逐步歸納

2、對分查找的基本思想和方法，確定解題步驟。情感態度與價值觀：通過實踐體驗科學解題的重要性，增強效率意識和全局觀念，感受對分查找算法的魅力，養成始終堅持、不斷積累才能獲得成功的意志品質。四、教學策略與手段1、教學線索：游戲引領-提出對分查找原理- 解析對分查找的算法特征-實踐解決問題。2、學習線索：分解問題-歸納問題-實踐提升，在三個階段的不斷推進中明確對分查找算法，總結規律。五、教學過程1、新課導入（1）熱身：游戲（2分鐘）找同學上來找一本上千頁電話冊里面的一個名字。(課程導入我寫的不是很詳細，自己設計哦)（2）教師引導：所以我不希望只有他一個人體驗這種方便，我們教室里還有一大幫人，其實這種什么

3、不止用于查找電話鋪，還可以運用到實際生活中，教室里有這么多人，坦白說，按學校的老方法一個人一個人的數，對所有老師來說都及其費力，那我們想想，是不是數數2368，這樣好點對嗎？。不要小看這種想法，他其實是非常棒的，他能把解決問題的時間縮短一半，因此我們提出了這種算法2、新課：首先我們一起來看一看折半查詢算法中的“折半”的含義。師：何為折半呢？生：減半；打一半的折扣。例如，我手里拿著一根繩子，現在我們來進行折半試驗，首先拿住繩子的兩個端點，然后從中點的位置進行對折，這樣繩子就縮短為原來長度一半，然后將一半的繩子繼續執行與剛才相同的操作，使得繩子的長度逐漸的縮短，直到繩子長度短得不能再進行折半了。師

4、：那什么時候就不能再折半了呢？生：即繩子的兩個端點合二為一為止。折半查找算法的思想與繩子折半的過程基本相同。下面我們先通過圖示來看看折半查找算法究竟是什么？教學步驟二：分解對分查找算法（5分鐘）假設一個從小到大排列的數據存放在一個數組中Data(10)，而查找數據存放在變量x中。如圖1所示，橙色方框的代表的是查詢數據x，每個淺蘭色方框代表的是數組中的每個元素，框內顯示的數據是每個數組元素對應的下標（序號），整排的淺蘭色方框就可以看成整個數組，即待查數據表（數組元素表）。x012345678910LowHigh圖一第一步：就像抓住繩子的兩端一樣，首先設立兩個標記Low、High分別來標識查詢區間

5、的低端和高端，即數組元素的下標，如圖1所示。師：對于初始查詢區間，它們是多少呢？生：Low=0 ， High=10第二步：取區間的中點標記Mid，如圖2所示。師：查詢區間的中點為多少？（這個地方，有的學生可能直接說出下標值，所以要提醒學生讓中點和兩個端點相聯系，即用端點表示中點）生：Mid=(Low+High)/2師：中點位置上的數據為什么？(提醒學生數據是放在數組Data中的) 生：Data( Mid) 012345678910MidLowHigh第三步：判斷中點位置上的數據Data( Mid)與要查找數x是否相等，如何相等，則找到，并結束查找；如果不相等，就執行第四步。師：這個判斷語句如何

6、寫呢？生：if Data( Mid)=x thenprint “x找到”結束查找end if第四步：如果不相等，那么對查詢區間進行折半操作。師：那如何折半是從中點處向左側折半還是向右側折半？（這是整個折半查詢進行下去的關鍵所在，所以一定要讓學生自己學會判斷）由于待找數據表是從小到大排列的，而且區間中點位置上的數據Date(Mid)也知道，所以，通過Data(Mid)與x的比較，看一看，x比Data(Mid)大還是小，就可以判斷出x落在中間數Data(Mid)的左側還是右側，從而判斷出向左還是向右折半。師：那么，判斷語句如何寫呢？生：if Data(Mid)High，停止折半查詢。0123456

7、78910LowHigh教學步驟四：對各種情況進行歸納總結。（1）x與data(mid)的大小比較影響i,j的取值的規律：i的取值規律：if data(mid)x then high=mid-1用分支結構實現。(2)繼續進行重復查找的條件： lowhigh，用循環結構實現。教學步驟五：構建對分查找的流程圖教學步驟六：對分查找算法的初步程序實現。YYN開始low1,high10計算middata(mid)=x?Nlowmid+1highmid-1N繼續查？輸出“未找到”Y輸出找到的信息結束lowhighmid=(low+high)2 data(mid)x?教師事先設計好Vb窗體，學生只需要在相應

8、的程序體輸入代表算法思想的關鍵語句。附主要程序體：Private Sub Command2_Click()Dim x As Integer, mid As Integer, low As Integer, high As Integerx = Val(Text1.Text)low = 0: high = 10Do While low = highmid = (low + high) 2If data(mid) = x ThenText2.Text = 找到了，是第 & mid & 個Exit SubEnd IfIf data(mid) data(mid),那么low=mid+1 否則 high

9、=mid+15、重復上述的3,4步，直到low超出j(或者理解為low=high不成立，所以不能用for next,而要用do while語句）6、如果有找到x,那執行第4步（1）步后應該輸出找到的位置后退出程序，如果不退出，說明x沒有找到，所以在相應位置要輸出“找不到”。折半查找算法基本思想總結（2分鐘）對一有序數據表，首先從初始查找區間開始，取出區間中點位置上的數據與要查詢數據進行比較，若相等，則查找成功，并結束查詢；否則，將當前查找區間縮小一半。在新的查詢區間內，同樣取出區間中點位置上的數據與要查詢數據進行比較，若相等，則查詢成功，并結束查詢，否則將新的查詢區間再次縮小一半。然后繼續采用相同的方法，直到查找數據成功或者查詢區間不能再折半（即查詢失敗）為止教學步驟七：評價。評價學生的程序實現情況，并討論或實踐問題：如果是降序序列，該怎么樣改動程序？如果序列元素不是10個，而是100個或更多呢？教學步驟八：總結提升。（1）由于對分查找過程中的每次比較都能使得搜索空間減半，對分查找將不會使用超過log2n次比較來找到目標值。（2）提升對分查找算法的實際意義：同學們可能還沒有意識到二分查找是多么高效，那不妨設想一下在一個包含一百萬個人名的電話簿中找一個名字，二分查找可以讓你不超過21次就能找到指定的名字。如果你能夠將世界上所有的人按照姓名排