1、,舊知回顧-對(duì)分查找,條件,被查找數(shù)據(jù)必須有序。,基本思想,首先將查找目標(biāo)與有序數(shù)組內(nèi)處于中間位置的元素進(jìn)行比較，如果中間位置上的元素值與查找目標(biāo)相同，表示找到； 否則根據(jù)數(shù)組元素的有序性，就可確定應(yīng)該在數(shù)組的前半部分還是后半部分繼續(xù)進(jìn)行查找，直到獲得最終結(jié)果。,舊知回顧-對(duì)分查找,1. 八名同學(xué)的成績從低到高依次為： 35,43,51, 60,72,77,86,90， 用對(duì)分查找找到72依次訪問到的數(shù)據(jù)是 。,60,77,72,熱身活動(dòng)現(xiàn)場(chǎng)演示,對(duì)分查找,算法與程序設(shè)計(jì),程序?qū)崿F(xiàn),周 玲 信息技術(shù) 杭州市富陽區(qū)新登中學(xué),1 流程圖-升序?yàn)槔?i=j？,jm-1,im+1,m(i+j)2,【小

2、組合作】 補(bǔ)充完整流程圖,2 程序?qū)崿F(xiàn),Key = Val(Text1.Text) i = 1 j = n Do While 計(jì)算出中間位置 If d(m) = Key Then Text2.Text = “在數(shù)組的”+ Str(m) +“號(hào)位置” Exit Do 查找成功立即終止循環(huán) End If If d(m) j then Text2.Text = 沒有找到,m=(i+j)2,i=m+1,j=m-1,i=j,3 小試身手,1. 在已排序的數(shù)組D中查找鍵值為Key的數(shù)，其對(duì)分查找的VB程序如下，請(qǐng)補(bǔ)充完整程序：,i=1 :j=n b=0 DO while ？ m=fix(i+j)/2) I

3、f d(m)=key then ？：exit do End If If key0 then text1.text=str(b) else text1.text=“沒有找到”,i=j,j=m-1,b=m,3 小試身手,i=1:j=n xb=0 Do While id(m) B. keyd(m) D. key=d(m),A,2. 在已排序的數(shù)組d(數(shù)組元素d(1) d(2) d(n) )中查找鍵值為key的數(shù)，其對(duì)方查找的VB程序段如下：,4 提高練習(xí),1.【加試題】某對(duì)分查找算法的VB程序段如下： i=1 ： j=9 : n=0 Key=Val(Text1.Text) Do While i =j

4、 n=n+1 m=Fix(i+j)/2) If key=d(m) Then Exit Do If keyd(m) Then j=m-1 Else i=m+1 Loop 數(shù)組元素d(1)到d(9)的值依次為”7,12,18,25,39,58,61,72,86”。 若該程序段運(yùn)行結(jié)束后，n的值為2，則key的值是（ ） A. 39 B. 18或61 C. 18或72 D.12或61,D,4 練一練,C,2.【加試題】數(shù)組元素啊a(1)到a(8)的值依次為“4,21,37,54,68,73,77,96”，利用如下對(duì)分查找的算法查找數(shù)據(jù)“75”，該代碼執(zhí)行后m , i, j 三個(gè)變量的值分別是（ ） i=1: j=8: x=75 Do While ix Then j=m-1 Else i=m+1 Loop A. m=6 i=6 j=6 B. m=7 i=6 j=7 C. m=