顺序查找和对分查找.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,查找,顺序查找和对分查找,查找,一种数据查询的技术,在数组变量中存储的一批数据中找出一个特定的数据,.,顺序查找,27,36,32,18,d(1),d(2),d(3),d(4),输入查找的元素值,key=32,i=1,i=2,i=3,此时,d(i)=key,数组中的第,3,个位置,如果输入查找的元素值,key=22,i=1,i=2,i=3,i=4,i=5,27,36,32,18,d(1),d(2),d(3),d(4),此时,i,等于,5,超过数组中元素个数,找不到,算法描述,取得要找的元素值,key,从数组的第,i,个位置开始找,(i,开始等于,1),如果,d(i)=key,则输出,i,并退出循环,否则,i,指向下一个位置,继续找,如果找到数组末尾还没找到,则输出找不到,.,转化成程序,Private Sub Command3_Click(),顺序查找,Key=Val(Text2.Text),i=1,Do While,If Then ,在第,i,个位置找到,Text3.Text=,在数组的第+,Str,(i)+,个位置,Exit Do ,找到了就退出循环,End If,Loop,If i=n+1 Then ,或者,if in then,Text3.Text=,在数组中没有找到+,Str,(Key),End If,End Sub,d(i)=Key,i=i+1,以,n,来表示数组中元素个数,i=n,开始,i=1,i=n?,Y,d(i)=key?,N,i=i+1,未找到，输出结果0,找到，输出,结果:,i,结束,Y,程序界面,(,可以在排序程序的基础上做,),text2,text3,command2,text4,command1,For I=1 to n,randomize,d(i)=fix(1000*,rnd,),Next i,怎样自动生成数据呢？,利用随机函数,rnd,():,产生0,1)之间的随机数,顺序查找分析,若一个数组有,n,个元素,找到第,1,个元素,查找,1,次,找到第,2,个元素,查找,2,次,找到第,n,个元素，查找,n,次,平均查找次数（,1+2+n,）,/n,（,n+1,）,/2,对分查找,在已经,排好序,的数组里进行查找,具体算法演示，观看,对分查找,.,swf,建议用单步运行,边解释边看运行过程,.,对分查找的基本方法是,在查找范围(,I,j),内，可以利用数据的有序性，而不必逐个地进行查找，计算查找范围的中点位置（例如使用变量,m,记录这个中点位置）。把查找范围(,I,j),的中点位置上的数据,d(m),与查找键,key,进行比较，结果必然是如下三种情况之一：,(1),keyd(m),与(1)相同的理由，必须在新的范围(,m+1,j),中继续查找。,这样除了出现情况(2)在通过一次比较后新的查找范围不超过上一次查找范围的一半。,对分查找分析,对分查找时每次都把查找范围缩小一半,因此平均的查找次数是,log,2,n,程序界面（,在上节课的基础上修改,）,command3,command4,代码分析,command4,的,click,过程,Key=Val(Text2.Text),i=1,j=n,Pos=0,Do While i=j,If d(m)=Key Then,pos=m,Exit Do,End If,If d(m)Key Then,Else,End If,Loop,If pos=0 Then,Text3.Text=,找不到+,Str,(Key),End If,m=(i+j)2,或,m=fix(I+j)/2),i=m+1,j=m-1,顺序查找与对分查找比较,是否需要,事先排序,平均查找次数,顺序查找,不需要,(n+1)/2,对分查找,需要,log,2,n,