对分查找

《对分查找》由会员分享，可在线阅读，更多相关《对分查找（13页珍藏版）》请在装配图网上搜索。

1、单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2018/5/29,#,对分查找（有序数组）,对分查找的基本思想：首先将查找键与有序数组内处于中间位置的元素进行比较，如果中间位置上的元素数值与查找键相同，表示找到，否则根据数组元素的有序性，就可确定应该在数组的前半部分还是后半部分继续进行查找。在新确定的范围内，继续按上述方法进行查找，直到获得最终结果。,对,分查找是一种效率很高的查找方法，但被查找的,数据必须是有序的,。,若用一个数组,d(1),到,d(11),来存放升序的元素序列，查找键,Key,为,12,6,12,15,18,22,25,28,35,46

2、,58,60,1,2,3,4,5,6,7,8,9,10,11,i,j,mid,Mid=(i+j)2,Keyd(mid),j=mid-1,若用一个数组,d(1),到,d(11),来存放升序的元素序列，查找键,Key,为,12,6,12,15,18,22,25,28,35,46,58,60,1,2,3,4,5,6,7,8,9,10,11,i,j,mid,Mid=(i+j)2,Keyd(mid),i=mid+1,若用一个数组,d(1),到,d(11),来存放升序的元素序列，查找键,Key,为,12,6,12,15,18,22,25,28,35,46,58,60,1,2,3,4,5,6,7,8,9,1

3、0,11,i,j,mid,Mid=(i+j)2,Key=d(mid),输出：,Mid=2,若用一个数组,d(1),到,d(11),来存放升序的元素序列，查找键,Key,为,12,6,12,15,18,22,25,28,35,46,58,60,6,12,15,18,22,25,28,35,46,58,60,6,12,15,18,22,25,28,35,46,58,60,6,12,15,18,22,25,28,35,46,58,60,6,12,15,18,22,25,28,35,46,58,60,1,2,3,4,5,6,7,8,9,10,11,i,j,i,j,min,j,i,min,i,j,min

4、,i,j,min,对,分查找算法程序实现,对分查找的程序结构（以查找升序序列为例）,如果区间未空，那么继续执行循环体（,一般用,do while,循环实现,）,循环尾,取中点,的,下标,如果中点就是目标，那么退出循环,如果目标小于中点，那么进入左半区间，否则进入右半区间,6,12,15,18,22,25,28,35,46,58,60,j,mid,i,Do while i=j,loop,m=fix(i+j)/2),If d(m)=key then,exit do,End if,If keyd(m)then,Else,End if,If xb0 then,text1.text=str(xb),El

5、se,text1.text=“,没有找到,”,End if,i=1:j=10,Xb=0,j=m-1,i=m+1,xb=m,对分查找算法变,式,key=val(Text1.text,),i,=1:j=n:c=0:found=False,found=False,表示还未找到,Do,While i=j and,found=False,found=False,也可以写成,not found,m=(i+j)2,取中间位置,c=c+1,If a(m)=key Then,found=True,找到后，改变标记,变量,ElseIf key a(m)Then,j=m,1,前半段找,Else,i =m+1,后半段

6、找,End If,Loop,If,found=True,then Text2.Text=Str(m)Else Text2.Text=,找不到,If found=True,等价于,If found,Text3.Text=,共查找了,+Str(c)+,次,顺序查找和对分查找比较,顺序查找不要求数组有序，效率较低，平均需要,(n+1)/2,次。,对分查找要求数组有序，效率较高，最多需要,int(log,2,n)+1,次。,顺序查找可以用,For,语句或,Do,语句来写，对分查找只能,用,Do,语句来写,P63,例,2,text1,labe2,labe3,X=val(text1.text),i=1:j=50:k=0:f=false,Do while(i=j)and not f,k=k+1,计算出中间位置,If x=a(m)then,f=true,Elseif xa(m)then,else,i=m+1,End if,Loop,If f then,label2.caption=“,此账号余额为,”+str(b(m)+,“,元,”,label3.caption=“,共查找,”+,+“,次,”,Else,label2.caption=“,找不到此账号，请重新输入,”,End if,End sub,