对分查找算法及程序实现课件

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,3.7,对分查找算法及程序实现,1,对分查找的概念,对分查找又称二分查找，是一种高效的查找方法。对分查找的前提是，被查找的数据序列是有序的,(,升序或降序,),。,对分查找的基本思想是在有序的数列中，首先将要查找的数据与有序数列内处于中间位置的数据进行比较，如果两者相等，则查找成功；否则就根据数据的有序性，再确定该数据的范围应该在数列的前半部分还是后半部分；在新确定的缩少范围内，继续按上述方法进行查找，直到找到要查找的数据，即查找成功，如果要查找的数据不存在，即查找不成功。,3.7 对分查找算法及程序实现1对分查找的概念,2,对分查找的过程,若,key,为查找键，数组,d,存放,n,个已按升序排序的数据。在使用对分查找时，把查找范围,i,，,j,的中间位置上的数据,d(m),与查找键,key,进行比较，结果必然是如下三种情况之一：,(1),若,keyd(m),，由与,(1),相同的理由，必须在新的范围,(m,1,，,j),中继续查找。,这样，除了出现情况,(2),，在通过一次比较后，新的查找范围将不超过上次查找范围的一半。,2对分查找的过程,中间位置数据,d(m),的下标,m,的计算方法：,m,(i,j)2,或,m,fix(i,j)/2),以规模为,16,的递增数组,d,为例，观察对分查找的过程。要查找的数据,key,为,37,。,中间位置数据d(m)的下标m的计算方法：m(ij)2,3,对分查找算法的表示,使用对分查找在数组变量,d,中查找,key,，用自然语言描述的算法如下：,(1)(,确定初始查找范围,)i1,，,jn,。,(2)(,是否能继续查找？,),如果,ij,，那么转到,(4),。,(3)(,找不到,),输入出结果,0,，算法结束。,(4)(,计算中点位置,)m(i,j)2,。,(5)(,相等？,),如果,d(m),key,，那么转到,(7),。,(6)(,修改查找范围,),如果,keyd(m),，那么,jm,1,；否则,im,1,，转到,(2),。,(7)(,找到,),输出结果,m,，算法结束。,3对分查找算法的表示,使用流程图描述对分查找的算法如下图所示：,使用流程图描述对分查找的算法如下图所示：,4,对分查找算法程序的实现要点,(1),由于比较次数难以确定，所以用,Do,语句来实现循环；,(2),在,Do,循环体中用,If,语句来判断查找是否成功；,(3),若查找成功则输出查找结果，并结束循环,(Exit Do),；,(4),若查找不成功，则判断查找键在数组的左半区间还是右半区间，从而缩小范围。,4对分查找算法程序的实现要点,对分查找的程序结构如下,(,升序序列,),：,对分查找的程序结构如下(升序序列)：,对分查找程序的基本框架：,Private Sub Command1_Click(),i,1:j,n,Do While i,j,m,(i,j)2,If d(m),Key Then,输出结果，退出查找,(,代码略,),ElseIf Key d(m)Then,j,m,1,Else,i,m,1,End If,Loop,End Sub,对分查找程序的基本框架：,查找次数的估算,对规模为,n,的数组进行对分查找时，无论是否找到，至多进行,log,2,n,1(log,2,n,表示大于或等于,log,2,n,的最小整数,),次查找就能得到结果，而使用顺序查找算法，在最坏的情况下,(,查找键在最后一个或没找到,),，需要进行,n,次查找，最好的情况是一次查找,(,查找键在第一个,),，平均查找次数是 。,查找次数的估算,本节的学习要求掌握对分查找算法的基本思想，掌握对分查找算法的程序实现要点，学会编写简单的对分查找的程序。掌握对顺序查找与对分查找次数的估算。对分查找算法在历次考试中出现的概率为,90%,以上，考查方式为选择题与填空题。,本节的学习要求掌握对分查找算法的基本思想，掌握对分查找算法的,1,下列有关查找的说法，正确的是,(,),A,顺序查找时，被查找的数据必须有序,B,对分查找时，被查找的数据不一定有序,C,顺序查找总能找到要查找的关键字,D,一般情况下，对分查找的效率较高,D,1下列有关查找的说法，正确的是 (,2,某网站报名参加免费三亚游的会员序列号有：,101,、,135,、,238,、,342,、,450,、,558,、,633,、,708,、,846,、,910,。采用对分查找，查找序列号为,846,号网友信息的过程中，依次被访问的序列号是,(,),A,450,、,708,、,846,B,450,、,708,、,910,、,846,C,558,、,708,、,846,D,558,、,708,、,910,、,846,A,2某网站报名参加免费三亚游的会员序列号有：101、135、,3,某电子图书馆网站有,10,万本图书记录,(,已索引排序,),，假设从中取出一条记录并与待查找项进行比较所花时间为,10,毫秒，则用对分法在该系统中查找任意一本指定图书最多花费的时间约为,(,),A,100,万毫秒,B,50,万毫秒,C,10,毫秒,D,170,毫秒,D,3某电子图书馆网站有10万本图书记录(已索引排序)，假设从,4,某数组有,7,个元素，依次为,158,、,234,、,369,、,478,、,552,、,697,、,748,。若采用对分查找法在该数组中查找数据,748,，需要查找的次数是,(,),A,1,B,2,C,3,D,4,C,4某数组有7个元素，依次为158、234、369、478、,5,在有序单词序列：,As,、,Book,、,Door,、,English,、,Floyd,、,Good,、,Hello,、,Sun,中，用对分查找法找到单词“,Good”,所需要的查找次数是,(,),A,1,B,2,C,3,D,4,B,5在有序单词序列：As、Book、Door、English,6,某,8,位男生的肺活量数据放在数组元素,a(l),到,a(8),中，其数据依次为“,3205,、,3408,、,3471,、,3498,、,3621,、,3829,、,4233,、,4540”,。使用对分查找，设定查找键,key,，若第一个被访问到的数据是,3498,，小于,key,值，则第二个被访问到的数据是,(,),A,3408,B,3829,C,4233,D,4540,B,6某8位男生的肺活量数据放在数组元素a(l)到a(8)中，,7,使用对分查找在已排序的数组,d(,数组元素,d(l)d(2),d(n),中查找,key,的算法流程图如下。其中、框中的内容分别是,(,),A,jm,1 im,1,B,jm,1 im,1,C,jm,1 im,1,D,jm,1 im,1,C,7使用对分查找在已排序的数组d(数组元素d(l)d(2),8,有两组数据：,54,、,31,、,43,、,12,、,8,、,73,、,56,、,34,、,89,、,60,、,23,、,67,87,、,83,、,75,、,70,、,63,、,59,、,55,、,37,、,33,、,21,、,17,、,7,下列有关查找方法描述不正确的是,(,),A,可以直接使用顺序查找,B,可以直接使用对分查找,C,可以直接使用对分查找,D,可以直接使用顺序查找,C,8有两组数据：C,9,某查找算法的部分,VB,程序代码如下：,t,False,i,0,Do While i a(i+1)Then k,k,1 Else k,1,(1),If k max Then k=max,(2),Next i,Text2.Text,Str(max),End Sub,a(i-1),(1)加框处应填入_。max=k,某学校把每个学生的姓名和家长联系电话保存到计算机中，以便遇到紧急情况时可以及时通知学生家长。每个学生的姓名和家长联系电话已经保存在数组,xm,和,phone(,都为字符串类型,),中。现在要设计一个根据输入的学生姓名查询该学生家长的联系电话的程序。程序运行时的界面如下图所示：,完善程序：下列程序运行时，在,Text1,中输入学生姓名，单击“查询家长电话”按钮,Command1,后，在标签,Label2,中显示对应的学生家长电话，若找不到则显示“未找到该学生”。程序代码如下：,某学校把每个学生的姓名和家长联系电话保存到计算机中，以便遇到,Dim xm(1 To 1000)As String,Dim phone(1 To 1000)As String,Const n As Integer,1000,Private Sub Command1_Click(),Dim x As String,Dim find As Boolean,Dim i As Integer,x,Text1.Text,i,0,find,False,Do While(i n)And find,False,If,Then find,True,Loop,If find,True Then,Label2.Caption,“,该学生家长联系电话为：,”,phone(i),Else,Label2.Caption,“,未找到该学生,”,End If,End Sub,Private Sub Form_Load(),学生姓名及家长电话数组赋初值语句，忽略,End Sub,请阅读代码并问答下列问题。,(1),解决此问题的算法是,_,。,在程序和划线处填入适当的语句或表达式，将程序补充完整：,(2),程序中划线处应填入,_,。,(3),程序中划线处应填入,_,。,注：该示例程序在素材文件夹下,vb33,文件夹中。,顺序查找算法,i=i+1,x=xm(i),Dim xm(1 To 1000)As String请阅读,12,某中学,2009,年下半年和,2010,年上半年各有,300,名和,100,名学生参加信息技术高考，下列,VB,程序用于统计参加过这两次考试的学生信息，其中,Command1_Click,过程的算法流程图如下所示：,12某中学2009年下半年和2010年上半年各有300名和,VB,程序代码如下所示：,Dim a(1 To 300)As String,用于存放,2009,年下半年考试学生的身份证号码,Dim b(1 To 100)As String,用于存放,2010,年上半年考试学生的身份证号码,Form Load,过程用于进行一些初始化准备工作,Private Sub Form_Load(),将参加,2009,年下半年考试学生的身份证号码放在数组,a,中,将参加,2010,年上半年考试学生的身份证号码放在数组,b,中,将数组,a,中数据升序排列,将数组,a,和数组,b,中的数据分别显示在列表框,List1,和,List2,中,代码略,End Sub,VB程序代码如下所示：,请回答下列问题：,(1),流程图中虚线框部分所采用的查找算法名称是,_,。,(2),加框处代码有错，应改为,_,。,(3),加框处代码有错，应改为,_,。,Command1_Click(),过程用于统计参加过这两次考试的学生信息,Private Sub Command1_Click(),Dim i As Integer,bot As Integer,top As Integer,m As Integer,For i=1 To 300,bot,1,top,300,Do While bot b(i)Then,m=bot-1,Else,bot,m,1,End If,Loop,Next i,End Sub,对分查找算法,For i=1 to 100,top=m-1,请回答下列问题：Command1_Click()过程用于统,13,按学号查找成绩。新生分班结束了，教务处将学生学号、学生班级和分班考试成绩录入到计算机中。为方便学生查询录取情况，编制了一个根据学生学号查找某位学生