高中信息技術(shù)選修1：算法與程序設(shè)計 2.4 查找-“黃岡杯”一等獎

猜價格：31——40玩一玩對分查找算法及程序?qū)崿F(xiàn)（1）對分查找是效率很高的查找方法，但前提是被查找的數(shù)據(jù)必須是有序的。（2）首先將查找的數(shù)與有序數(shù)組內(nèi)處于中間位置的數(shù)據(jù)比較，如果中間位置上的數(shù)與查找的數(shù)不同，根據(jù)有序性，就可確定應(yīng)該在數(shù)組的前半部分還是后半部分繼續(xù)查找。（3）在新確定的范圍內(nèi)，繼續(xù)按上述方法進行查找，直到獲得最終結(jié)果。對分查找算法原理m=(i+j)\2m=Fix（（i+j）/2）m=Int（（i+j）/2）用數(shù)組d（1to10）存放升序的數(shù)字序列i表示查找范圍第一個數(shù)組元素下標（起始位置）j表示查找范圍最后一個數(shù)組元素下標（終止位置）m表示查找范圍內(nèi)中間位置數(shù)組元素的下標（中間位置）分解對分查找過程m=(i+j)\2d(1)d(2)d(3)d(4)d(5)d(6)d(7)d(8)d(9)d(10)10151718222735454852key=48查找次數(shù)ijmd(m)第一次110522m=(i+j)\2d(1)d(2)d(3)d(4)d(5)d(6)d(7)d(8)d(9)d(10)10151718222735454852key=48查找次數(shù)ijmd(m)第一次110522第二次610845m=(i+j)\2d(1)d(2)d(3)d(4)d(5)d(6)d(7)d(8)d(9)d(10)10151718222735454852key=48查找次數(shù)ijmd(m)第一次110522第二次610845第三次910948找到了總結(jié)規(guī)律每次d(m)與Key比較會確定下一次查找范圍i的取值規(guī)律：j的取值規(guī)律：用對分查找算法查找數(shù)據(jù)（以升序數(shù)列為例）i=m+1j=m-1d(m)<keyd(m)>key

完成導(dǎo)學(xué)案上查找17表格的填寫m=(i+j)\2d(1)d(2)d(3)d(4)d(5)d(6)d(7)d(8)d(9)d(10)10151718222735454852key=17查找次數(shù)ijmd(m)第一次110522第二次14215第三次34317找到了m=(i+j)\2d(1)d(2)d(3)d(4)d(5)d(6)d(7)d(8)d(9)d(10)10151718222735454852key=20查找次數(shù)ijmd(m)第一次110522第二次14215第三次34317第四次44418找不到第五次54總結(jié)規(guī)律根據(jù)i，j的初值，計算出中間位置m，比較Key與d(m)，相等則輸出，否則確定新i或新j，直到找到為止，這樣重復(fù)操作可以采用什么結(jié)構(gòu)？循環(huán)結(jié)構(gòu)繼續(xù)進行重復(fù)查找的條件？i<=jDowhilei<=j

loopYYN開始i

1,j

10計算md(m)=key?Nd(m)<key?i

m+1N繼續(xù)查找？輸出“未找到”Y輸出找到的信息結(jié)束i<=jm

(i+j)\2?jm-1對分查找流程圖輸入查找鍵key

m=(i+j)\2Ifd(m)=keyThenLabel2.Caption=Str(m)ExitDo'跳出循環(huán)

EndIfIfd(m)<keyTheni=m+1Elsej=m–1EndIfIf語句格式DimkeyAsInteger,mAsInteger,iAsInteger,jAsInteger________________'獲得要查找數(shù)據(jù)key的值________________'分別對i,j賦初值

DoWhilei<=j________________’求中間位置m的值

Ifd(m)=keyThenLabel2.Caption=Str(m)ExitdoEndIfIfd(m)<keyThen________________’求i的值

Else________________’求j的值

EndIfLoopIfi>jThenLabel2.Caption="找不到！"key=val(text1.text)i=1:j=10m=(i+j)\2i=m+1j=m-1對分查找算法程序?qū)崿F(xiàn)對分查找算法實施前提：有序數(shù)字序列中點位置的計算：（i+j)\2新的查找范圍的確定i=m+1或者j=m-1查找結(jié)束的判定條件：找到數(shù)據(jù)或者i>jd(1)d(2)d(3)d(4)d(5)d(6)d(7)d(8)Key1015171822273545次數(shù)d(1)d(2)d(3)d(4)d(5)d(6)d(7)d(8)d(9)Key101517182227354548次數(shù)數(shù)組中每個數(shù)據(jù)的查找次數(shù)：32313234323413234對分查找算法的最多查找次數(shù)由于對分查找過程中的每次比較都能使搜索范圍減半，根據(jù)規(guī)律可以得出：[log2n]+1數(shù)組中每個數(shù)據(jù)的查找次數(shù)：1、前提：數(shù)據(jù)是有序的2、結(jié)束條件：i>j3、如果d(m)<keyi=m+1d(m)>keyj=m-14、n個數(shù)據(jù)最多查找次數(shù)：[log2n]+1

對分查找課堂總結(jié)：TheEnd

塊If語句的格式單一條件可以這樣寫if<條件>then語句塊1endif雙條件這樣寫if<條件>then

語句塊1else

語句塊2endif

多條件

if<條件>then

語句塊1elseif<條件>then

語句塊2elseif<條件>then

語句塊3(省略)