3.3.3二分法查找.doc

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