1、德清一中 楊月霞對分查找算法復習前提：前提是被查找的數(shù)據必須是 的（遞增/遞減）意義：對分查找的高效性。試想：將全國13億人按身份證號排列后，你可在31次比較 后找到這個人的信息。 若用順序查找還有這個效率嗎？有序Key = Val(Text1.Text)i = 1:j = n：p=0Do While i = j m=(i+j)2 If a(m) = Key Then p=m:Exit Do Else If a(m) Key Then Else End IfLoop 對分查找的核心代碼：（以n個元素的遞增數(shù)組為例） i=m+1j=m-1Dim a(1 to n) as integer,當n=1

2、0時數(shù)組元素排列如下：a(1)a(2)a(3)a(4)a(5)a(6)a(7)a(8)a(9)a(10)1347111619202730第一次a(1)1a(2)3a(3)4a(4)7a(5)11a(6)16a(7)19a(8)20a(9)27a(10)30第二次a(1)1a(2)3a(3)4a(4)7a(5)11m=5a(6)16a(7)19a(8)20a(9)27a(10)30第三次a(1)1a(2)3a(3)4a(4)7a(5)11m=5a(6)16i=6a(7)19a(8)20a(9)27a(10)30第四次非法區(qū)間a(2)3a(3)4a(4)7a(5)11m=5a(6)16i=6a(7

3、)19a(8)20a(9)27i=9m=9a(10)30key=26i=1j=10m=5i=6j=10m=8i=9m=9j=10j=8對分查找一般過程歸納（以n個元素的遞增數(shù)組為例）：1、i的初值=1； j的初值=n2、中間數(shù)的下標m與i，j的關系是：m=Int(i+j)/2)3、確定退出循環(huán)的條件 區(qū)間的二個端點 i,j必須滿足的條件是id(m)，說明應在下半區(qū)繼續(xù)查找，修改i 還 是j? i=m+1 若keyd(m)，說明應在上半區(qū)繼續(xù)查找，修改i 還 是j? j=m-1 1. (必做）數(shù)組變量d（1）到d（8）的值依次為87、76、69、66、56、45、37、23，用“對分查找”找到“

4、69”的過程中，依次被訪問到的數(shù)據是（）A69B66、69C66、76、69D56、66、76、69熱身訓練2.（選做）在有序單詞序列bike,cake,data,easy,feel, great,hive,mark, sweet中,用對分查找算法找到 easy過程中,依次被訪問到的數(shù)據為feel, data. easygreat, data, easybike, cake, data, easy feel. cake. data, easy對分查找考點分析：（一）常規(guī)考點（二）數(shù)組元素下標值的變化規(guī)律（變量跟蹤法）（三）搜索區(qū)間長度和查找次數(shù)（四）表達式的改變和查找成功后的處理方法對結果的影

5、響1. 某對分査找算法的VB程序段如下:i = 1: j = 9: n = 0key = Val(Textl.Text)Do While i = j n = n + 1 m = Fix(i + j) / 2) If key = d(m) Then Exit Do If key d(m) Then j = m - 1 Else i = m + 1Loop數(shù)組元素d(1)到d（9）的值依次為“7，12，18，25，39，58，61，72，86”。若該程序段運行結束后，n的值為2，則key的值是A.18或72 B. 12或61 C.39 D. 7或58（一）常規(guī)考點寫出每一次循環(huán)結束后m,i,j,p

6、的值對分查找核心程序當Key=1時開 始：m=0,i=1,j=10,p=0第一次：第二次：第三次：Key = Val(Text1.Text)p=0:i = 1:j = nDo While i = j m=(i+j)2 If a(m) = Key Then p=m:Exit Do Else If a(m) Key Then i=m+1 Else j=m-1 End IfLoop 思考：循環(huán)結束時p=0意味著什么？當Key=20時開 始：m=0,i=1,j=10,p=0第一次：第二次：當Key=21時開 始：m=0,i=1,j=10,p=0第一次：第二次：第三次：a(1)a(2)a(3)a(4)a

7、(5)a(6)a(7)a(8)a(9)a(10)1347111619202730（二 ）數(shù)組元素下標值的變化規(guī)律（變量跟蹤法）寫出每一次循環(huán)結束后m,i,j,p的值對分查找核心程序當Key=1時開 始：m=0,i=1,j=10,p=0第一次：m=5,i=1,j=4,p=0第二次：m=2,i=1,j=2,p=0第三次：m=1,i=1,j=1,p=1Key = Val(Text1.Text)p=0:i = 1:j = nDo While i = j m=(i+j)2 If a(m) = Key Then p=m:Exit Do Else If a(m) Key Then i=m+1 Else j=

8、m-1 End IfLoop 當Key=20時開 始：m=0,i=1,j=10,p=0第一次：m=5,i=6,j=10,p=0第二次：m=8,i=6,j=10,p=8當Key=21時開 始：m=0,i=1,j=10,p=0第一次：m=5,i=6,j=10,p=0第二次：m=8,i=9,j=10,p=0第三次：m=9,i=9,j=8,p=01. (必做）某對分查找算法的VB程序段如下：i=1: j=6: n=0: f=Falsekey=val(Text1.Text)Do while i=j and f=False n=n+1 m=(i+j)2 If key=d(m) then f=True If

9、 keyd(m) then j=m-1 Else i=m+1Loop數(shù)組元素d(1)到d(6)的值依次為“13，18，25，30，35，59”。文本框Text1中輸入33后運行該程序，運行結束后下列說法不正確的是（ ）變量f的值為False變量i的值為5C. 變量m的值為4D. 變量n的值為2（二）數(shù)組元素下標值的變化規(guī)律（變量跟蹤法）2.（選做）已知一無序數(shù)組a（下標1到n），通過引入數(shù)組b（下標1到n），使得a(b(1)a(b(2) a(b(3)a(b(n)（示例如圖所示），對這些有序數(shù)據可進行對分查找。則第一次查找時，中點位置m與中點值分別是A. m的值是Fix(1+n)/2),中點值是

10、 a(m)B. m的值是Fix(1+n)/2),中點值是 a(b(m)C. m的值是Fix(b(1)+b(n)/2),中點值是 a(m)D. m的值是Fix(b(1)+b(n)/2),中點值是 a(b(m)（二）數(shù)組元素下標值的變化規(guī)律（變量跟蹤法）對分查找算法的最多查找次數(shù)： Log2N+1查找次數(shù)剩余搜索區(qū)間1N/22N/223N/23mN/2m（三）搜索區(qū)間長度和查找次數(shù)1. (必做）某公司的員工管理系統(tǒng)中有1200條員工記錄（每條員工記錄已按員工編號升序排序），現(xiàn)用對分查找法搜索一員工信息，開始搜索的記錄范圍為1200條，若第5次對分查找后還需繼續(xù)搜索，則第6次搜索的記錄范圍內的記錄數(shù)

11、為（）18 19 37 752.（選做）有一個由4000個整數(shù)構成的順序表，假定表中的元素已經按升序排列，采用對分查找查找一個元素，則最多需要（ ）次比較就能確定是否存在所查找的元素A.11 B.12 C.13 D.14（三）搜索區(qū)間長度和查找次數(shù)（四）表達式的改變和查找成功后的處理方法對結果的影響1. (必做）Randomizekey = Int (Rnd*100)i = 1: j = 7s = Do While i = j m = (i + j) 2 If key = a(m) Then s=s+M : Exit Do End IfIf key a(m) Then j = m 1: s=s

12、+“L Else i = m + 1: s=s+“RLoopText1.Text =s數(shù)組元素a(1)到a(7)的值依次為“25,36,39,42,47,66,78”，執(zhí)行該程序段,文本框Text1中顯示的內容是“RLR，則可以確定隨機產生的Key值范圍是（ ）A（25，36）B（47，66）C（66,78)D(78,100)（四）表達式的改變和查找成功后的處理方法對結果的影響2. （選做）已知數(shù)組元素a(1)到a(9)的值依次為19,28,37,46,55,64,73,82,91,若在 Text1中輸入29,然后執(zhí)行以下程序段Key= Val(Text1.Text)10Text2.Text=

13、“ “i=1: j=9: f=FalseDo While i Key Then i=m+1 Else j=m-1 End IfText2. Text= Str(m)+Text2. TextLoop則在執(zhí)行該程序段后,Text2中示的內容是A.5 7 8B.55 37 28 C.82 73 55D.8 7 5 對分算法幾個注意問題： （1）對分查找的前提：被查找數(shù)據必須是有序的。 （2）新的查找范圍的確定：i=m+1 或 j=m-1 （3）數(shù)組元素下標值的變化規(guī)律 （4）表達式的改變和查找成功后的處理方法對結果的影響 （5）對分查找算法的最多查找次數(shù)： Log2n+1課堂小結 數(shù)組a 為一組正整數(shù)，奇數(shù)在前，偶數(shù)在后。奇數(shù)與偶數(shù)已分別按升序排序。依據對分查找思想：設計一個在數(shù)組a 中查找數(shù)據Key 的程序。實現(xiàn)該功能的VB 程序段如下：i = 1: j = 10Key = Val(Text1.Text)Do While i j Then s = 沒有找到！ Else s = 位置： + Str(m)Text2.Text = s上述程序中方框處可選語句為：i = m + 1j = m - 1If Key a(m) Then j = m - 1 Else i = m + 1則（1）、（2）、