查找复习课件新公开课.pptx

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2020/11/30 Monday,#,LC,查找算法复习,泰,顺中学,某次数学竞赛，共有,100,个选手参加比赛，为了公平起见，每位选手随机抽取一个号码牌，并根据号码牌找到对应的位置就坐,（如图所示）,。,假如你的号码牌是,28,，怎样,找到对应位置,？,查找,过程,从数组,d,的第1个元素,d(1),开始，依次判断各元素的值是否与查找键,key,的值,相等。,若某个数据和给定,的号码牌,相等,，则查找成功,，输出对应的位置,若一直到,最后,都找不到该号码牌，则输出“错误的号码牌,”,信息,Private Sub Command1_Click(),顺序查找,Dim key As Integer,i As Integer,Dim c As Integer c,记录查找次数,key=Val(Text1.Text),For i=,1,To,n,If d(i)=key Then _,_,Next i,If _,_ Then,T2.Text=,错误的号码牌,End If,Text3.Text=Str(c),End,Sub,顺序查找代码：,从数组,d,的第1个元素,d(1),开始，依次判断各元素的值是否与查找键,key,的值相等。,若某个数据和给定,的号码牌相等,，则查找成功,，输出对应的位置,若一直到最后都找不到该号码牌，则输出“错误的号码牌,”,信息,顺序查找平均查找（比较）次数,:,(n+1)/2,图,1,图,2,假如你的号码牌是,28,，图,2,数据中怎样,快速,找到,位置？,把对分查找程序代码补充完整：,Private Sub Command1_Click(),对分查找,Dim key As Integer,i As Integer,j As Integer,c As Integer c,记录查找次数,i=1:j=n:key=Val(Text1.Text),Do While i=j,_,c=c+1,If d(m)=key Then,_,ElseIf,_,Then,i=m+1,Else,jm-1,End If,Loop,If,_,Then T2.Text=,错误的号码,牌,“,Text3.Text,=Str(c),End Sub,Discussion,:,画出,key=18,的,查找示意图,并回答,以下,四,个,问题,。,总结二：,如果,d(m)key,新查找范围为上半部分,i,值不变，,j=m-1,继续进行重复查找的条件：,i=j,Question2:,当,d(m)key,时，新查找的范围在哪里？,i,和,j,如何变化？,10,15,17,18,22,d(1),d(2),d(3),d(4),d(5),Log,2,n,+1,i,j,m,把对分查找程序代码补充完整：,Private Sub Command1_Click(),对分查找,Dim key As Integer,i As Integer,j As Integer,c As Integer c,记录查找次数,i=1:j=n:key=Val(Text1.Text),Do While i j,d,(m)key,同题,3,若在查找前，其中号码牌先按从小到大的顺序存储在,d,数组中，位置存储在,a,数组中。程序界面如图所示，在文本框,Text1,中输入号码牌，,单击,“,变形,对,分查找,按钮，电脑就开始查找该号码牌对应的位置，如果找到对应的号码牌数字，就在文本框,t2,中显示该号码牌对应的位置信息，如果没有找到，则在文本框,t2,中显示与待查找号码牌,最接近的整数,对应的位置（当最接近的数有两个时，输出,较大数对应的位置,）,（,2017,年,4,月选考）【加试题】某对分查找算法的,VB,程序段如下：,key=Val(Text1.Text),i=1:j=10,Text2.Text=,Do While i=j,m=Int(i+j)/2+0.5),If key=a(m)Then Exit Do Exit Do,表示退出循环,If key a(m)Then j=m-1 Else i=m+1,Text2.Text=Text2.Text+Str(a(m),Loop,数组元素,a(1),到,a(10),的值依次为“8,17,24,30,36,40,55,58,61,66,”，文本框,Text1,中输入的值是,30,，执行该程序段，文本框,Text2,中显示的,是,A.40 24 B.40 24 36 30 C.40 24 36 D.36 17 24,考题展示,考题展示,【加试题】,某对分查找算法的,VB,程序段如下：,i=0:j=8,：,k=Val(Text1.Text),Do While i=j,m=Int(i+j)2+0.5),If k=b(m)Then,Exit,Do,else,If,kb(m)Then,j,=m,Else,i,=m+,1,end if,End if,Loop,数组元素,b(0)到,b(8),存储参加比赛同学的编号，值依次为“,5,8,11,21,32,39,56,65,72,”，经过该程序段段“加工”查找编号为,8,号同学的过程中，依次访问到的编号是,A,32 8 B,21 8C,32 11 8 D,39 21 8,7.,【加试题】,某对分查找算法的,VB,程序段如下：,key=Val(Text1.Text),n=0:i=1:j=7,flag=false,Do While i=j and flag=false,n=n+1,m=fix(i+j)/2),If key=a(m)Then flag=true,If,key a(m)Then i=m+1 Else j=m-1Text2.Text=Text2.Text+Str(a(m),Loop,数组元素,a(1),到,a(7),的值依次为“,89,72,68,45,23,19,17,”，文本框,Text1,中输入的值是,19,，执行该程序段后，下列变量的值不正确的是,A,n=2 B,m=6 C,i=5 D,j=7,考题展示,8.,（变形）,【加试题】,某对分查找算法的,VB,程序段如下：,key=Val(Text1.Text),n=0:i=1:j=7,flag=false,Do While i=j and flag=false,n=n+1,m,=fix(i+j)/2),If,key=a(m),Then,flagtrue,elseIf,key a(m),Then,i=m+1,Else,j,=m,1,end if,Text2.Text=Text2.Text+Str(a(m),Loop,数组元素,a(1),到,a(7),的值依次为“,89,72,68,45,23,19,17,”，文本框,Text1,中输入的值是,19,，执行该程序段后，下列变量的值不正确的是,A,n=2 B,m=6,C,i=5,D,j=5,考题展示,拓展练习：,挑战,1,：,如果在代码中引进布尔变量，怎样来完成“查找失败”部分的代码设计？,Private Sub Command1_Click(),对分查找,Dim key As Integer,i As Integer,j As Integer,c As Integer,i,=1:j=n:key=Val(Text1.Text),Do While i key,Then,i=m+1,Else,j=m-1,End If,Loop,If,ij,Then,T2.Text=,错误的号码,牌,“,Text3.Text,=Str(c),End Sub,find as,boolean,:,find=false,find=True,flag=false,And not find,相关程序,课堂小结,是否有序,查找次数,效率,顺序查找,对分查找,不做要求,必须有序,最少,1,次，最多,n,次，平均查找次数（,n+1,）,/2,最多,log,2,n+1,次,较低,较高,一、两种算法的简单比较,1.,对分算法几个注意问题：,（,1,）对分查找的前提：被查找数据必须是,有序,的。,（,2,）新的查找范围的确定：,i=m+1,或,j=m-1,（,3,）查找结束的判断条件：找到数据,(,find=true,),或,ij,2.,对分查找算法的最多查找次数：,Log,2,n,+1,课后任务：,如果在代码中引进布尔变量，怎样来完成“查找失败”部分的代码设计？,对分查找,Thank You,！,LC,