3.3.3二分法查找.doc

二分法查找導學案1、 課前自主學習自主閱讀課本PP頁，完成自主檢測。1、 什么是二分法查找？ 2、 二分法查找的要求是什么？ 3、 如何利用二分法查找數據？ 4、與同學交流，討論后，請列舉一兩個生活中用二分法查找的案例。2、 體驗猜數字游戲1、 創(chuàng)設情景，激發(fā)興趣，導入課題。大家知道中央電視臺有一檔收視率很高的節(jié)目叫“幸運52”，其中有一個環(huán)節(jié)，是讓選手猜商品的價格，規(guī)則是給出商品的價格范圍，主持人根據實際價格和選手報價給出提示：“高了”、“低了”、“正確”。曾經有一個選手，僅僅嘗試猜了3次，就猜出了實際價格。當時給出的價格范圍是100-300，實際價格是225。他猜的3個數是200（主持人：低了）、250（高了）、225（正確）。我們仔細分析這個選手的猜數過程，可以發(fā)現(xiàn)每次猜的數都是相應范圍中間的數，這實際上采用了“二分法查找”的算法思想?！救蝿找弧繂覸B，選“現(xiàn)存”-“桌面” “二分法查找練習”文件夾下的的計算機猜數.vbp文件，體驗游戲。 【思考討論，小組探究】提出問題1：計算機猜數游戲中究竟是怎樣查找的？ 是通過什么方法快速的猜出數字呢？提出問題2： 如果沒有順序則能否進行二分查找？這說明二分查找對待查數據序列有什么要求？3、 教師講解分析從被猜商品的價格范圍100-300，將100設為下界，300設為上界，取上下界的中間元素200與實際值225進行比較，200比225??；將200右邊相鄰的數201設為下界，上界還是300，取上下界的中間元素250與225進行比較，250比225大；將249作為上界，下界還是201，取上下界的中間元素225與225比較，正確，猜中?！舅伎加懻摚〗M探究】提出問題3： 請根據二分法算法的思想，將流程圖補充完整【任務二】啟動VB，打開桌面上的查找數字.vbp文件，嘗試修改源代碼。 要求：完善程序 ，要求實現(xiàn)8個數據元素的逐一賦值，并查找輸入的關鍵值在不在數組中?Private Sub Form_Click()Dim i, low, high, mid, key, a(7) As IntegerFor i = 0 To 7 for 循環(huán)為數組賦值 a(i) = InputBox(請依次輸入8個數組元素)Next ikey = 70 設置關鍵值，設置下界和上界的初始值low = 0: high = 7Do While 繼續(xù)查找的條件是什么? mid = 如何計算中間值？ If a(mid) = key Then Print 查找成功 如果中間值等于關鍵值，則找到了，直接退出Do循環(huán) Exit Do Else If keya(mid) Then 否則判斷關鍵值在左半部還是右半部 low = 如果關鍵值大于中間元素，則落在右半部，應重新設置什么？Else high = 否則，則落在左半部，應重新設置什么？ End If End If Loop 再次查找 If low high Then Print 查找不成功 End IfEnd Sub舉一反三想一想：用拼音法查字典，如何快速定位到漢字拼音首字母所在的位置？ 小組合作，利用以下字母表，分別觀察用這種逐步二分的方法定位到字母C和字母S時low,high和mid的變化情況，回答以下問題 ：highmidlowhigh【思考討論，小組探究】提出問題4：1.如果key a(m) Then 目標和關鍵值不匹配,重新設置下界或上界 Low = m + 1 落在右半部分 Else High = m - 1 落在左半部分 End If End If Loop If Low = High Then