對(duì)分查找算法鞏固復(fù)習(xí)公開(kāi)課教案教學(xué)設(shè)計(jì)課件案例試卷

對(duì)分查找算法鞏固提升對(duì)分查找算法歷次考試2015年10月——11題：查找范圍問(wèn)題2016年4月——12題：利用索引數(shù)組進(jìn)行對(duì)分查找2016年10——12題：已知查找次數(shù)，判斷key值2017年4月——11題：已知Key值，判斷輸出結(jié)果2017年11月——12題：Key為隨機(jī)值，判斷輸出結(jié)果2018年4月——12題：根據(jù)key的奇偶性，確定查找范圍2018年11月——16題：在左右交替上升的數(shù)據(jù)中對(duì)分查找2019年4月——12題：查找相鄰兩個(gè)元素的最大差值2020年1月——12題：Key值未知，判斷可能的查找次數(shù)及訪問(wèn)到的元素2020年7月——11題：Key值和數(shù)組元素未知，判斷依次訪問(wèn)元素的位置2021年1月——12題：Key值和數(shù)組元素未知，判斷依次訪問(wèn)的元素對(duì)分查找實(shí)現(xiàn)：key=Text1.Texti=1:j=nDoWhilei<=jm=(i+j)\2ifkey=a(m)ThenExitdo

Elseifa(m)>keyThen

j=m-1

Else

i=m+1EndifPrinti,j,mLoop對(duì)分查找核心代碼（數(shù)組d，規(guī)模為n,升序）key=Text1.Texti=1:j=n:Flag=FalseDoWhilei<=jAndNotFlagm=(i+j)\2ifkey=a(m)ThenFlag=true

Elseifa(m)>keyThenj=m-1

Elsei=m+1

EndIf

Printi,j,mLoopkey=Text1.Texti=1:j=n:Flag=FalseDoWhilei<=jAndNotFlagm=(i+j)\2ifkey=a(m)ThenFlag=Trueifa(m)>keyThenj=m-1Elsei=m+1

EndIf

Printi,j,mLoop對(duì)分查找特點(diǎn)：1.數(shù)組有序(局部有序)Int(Log2n)+12.最多查找次數(shù)：注意：key=a(m)時(shí)繼續(xù)查找的范圍例1：根據(jù)Key值查找該數(shù)據(jù)在數(shù)組中最后出現(xiàn)的位置L=1:R=10:n=10:Key=75′a(1)-a(10)的值分別為：86,78,77,75,75,75,60,54,54,51DoWhileL<=Rm=Fix((L+R)/2)If

①

ThenL=m+1

ElseR=m-1

EndIfLoopLabel1.Caption=Str(L-1)

在有重復(fù)數(shù)據(jù)的數(shù)組中（降序）,根據(jù)Key值查找該數(shù)據(jù)在數(shù)組中最先出現(xiàn)的位置Key<=a(m)Key<a(m)找不到或查找最先(后)出現(xiàn)的元素時(shí)（中途不退出）Int(Log2n)≤最少查找次數(shù)≤Int(Log2n)+1對(duì)分查找選擇題做題方法：

一、key已知，直接代入查找；

二、二叉樹(shù)解題

(P207.T5)5.某對(duì)分查找算法的VB程序段如下：i=1:j=6:f=Falsekey=Val(Text1.Text)DoWhilei<=jandf=Falsem=(i+j)\2Ifkey=a(m)thenf=True

Ifkey<a(m)thenj=m-1Elsei=m+1Loop數(shù)組元素a(1)到a(6)的值依次為“11，19，25，31，47，58”。文本框Text1中輸入“31”后運(yùn)行該程序，則以上程序段運(yùn)行結(jié)束后,下列說(shuō)法不正確的是A.變量f的值為T(mén)rueB.變量i的值為4