《对分查找算法巩固复习公开课教案教学设计课件案例试卷.pptx》由会员分享，可在线阅读，更多相关《对分查找算法巩固复习公开课教案教学设计课件案例试卷.pptx（11页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、对分查找算法巩固提升对分查找算法历次考试2015年10月11题：查找范围问题2016年4月12题：利用索引数组进行对分查找2016年1012题：已知查找次数，判断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值和数组元
2、素未知，判断依次访问的元素对分查找实现：对分查找实现：key=Text1.Textkey=Text1.Texti=1:j=ni=1:j=nDo While i=jDo While ikey Then Elseif a(m)key Then j=m-1 j=m-1 Else Else i=m+1 i=m+1 End if End if Print i,j,m Print i,j,mLoopLoop对分查找核心代码（数组对分查找核心代码（数组d d，规模为，规模为n,n,升序）升序）key=Text1.Textkey=Text1.Texti=1:j=n:Flag=Falsei=1:j=n:Flag
3、=FalseDo While i=j And Not FlagDo While ikey Then Elseif a(m)key Then j=m-1 j=m-1 Else Else i=m+1 i=m+1 End If End If Print i,j,m Print i,j,mLoopLoopkey=Text1.Textkey=Text1.Texti=1:j=n:Flag=Falsei=1:j=n:Flag=FalseDo While i=j And Not FlagDo While ikey Then if a(m)key Then j=m-1 j=m-1 Else Else i=m+1
4、 i=m+1 End If End If Print i,j,m Print i,j,mLoopLoop对分查找特点：1.数组有序(局部有序)Int(LogInt(Log2 2n n)+1)+12.最多查找次数：注意：注意：key=a(m)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,51Do While L=R m=Fix(L+R)/2)If Then L=m+1 Else R=m-1 End If Loop La
5、bel1.Caption=Str(L-1)在有重复数据的数组中（降序）,根据Key值查找该数据在数组中最先出现的位置Key=a(m)Key=a(m)Keya(m)Keya(m)找不到或查找最先(后)出现的元素时（中途不退出）Int(LogInt(Log2 2n n)最少查找次数 Int(Log Int(Log2 2n n)+1)+1对分查找选择题做题方法：一、key已知，直接代入查找；二、二叉树解题(P207.T5)(P207.T5)5.5.某对分查找算法的 VB程序段如下：i=1:j=6:f=False key=Val(Text1.Text)Do While i=j and f=False m=(i+j)2 If key=a(m)then f=True If keya(m)then j=m-1 Else i=m+1 Loop 数组元素a(1)到a(6)的值依次为“11，19，25，31，47，58”。文本框 Text1 中输入“31”后运行该程序，则以上程序段运行结束后,下列说法不正确的是A.变量f的值为True B.变量i的值为4 C.变量j的值为4 D.变量m 的值为3B做题方法：做题方法：keykey已知，代入直接查找即可。已知，代入直接查找即可。D做题方法：二叉树解题。做题方法：二叉树解题。2021年1月选考卷12题C