对分查找算法巩固复习公开课教案教学设计课件案例试卷

对分查找算法巩固提升对分查找算法历次考试2015年10月——11题：查找范围问题2016年4月——12题：利用索引数组进行对分查找2016年10——12题：已知查找次数，判断key值2017年4月——11题：已知Key值，判断输出结果2017年11月——12题：Key为随机值，判断输出结果2018年4月——12题：根据key的奇偶性，确定查找范围2018年11月——16题：在左右交替上升的数据中对分查找2019年4月——12题：查找相邻两个元素的最大差值2020年1月——12题：Key值未知，判断可能的查找次数及访问到的元素2020年7月——11题：Key值和数组元素未知，判断依次访问元素的位置2021年1月——12题：Key值和数组元素未知，判断依次访问的元素对分查找实现：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对分查找核心代码（数组d，规模为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对分查找特点：1.数组有序(局部有序)Int(Log2n)+12.最多查找次数：注意：key=a(m)时继续查找的范围例1：根据Key值查找该数据在数组中最后出现的位置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)

在有重复数据的数组中（降序）,根据Key值查找该数据在数组中最先出现的位置Key<=a(m)Key<a(m)找不到或查找最先(后)出现的元素时（中途不退出）Int(Log2n)≤最少查找次数≤Int(Log2n)+1对分查找选择题做题方法：

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

二、二叉树解题

(P207.T5)5.某对分查找算法的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数组元素a(1)到a(6)的值依次为“11，19，25，31，47，58”。文本框Text1中输入“31”后运行该程序，则以上程序段运行结束后,下列说法不正确的是A.变量f的值为TrueB.变量i的值为4