查找算法课件.ppt

顺序查找和对分查找查找是一种查询数据的技术,其目标是能以比较少的步聚和较短的时间找到所需的对象。顺序查找的基本思想是从第一个数据开始,按数据的顺序逐个将数据与给定的值进行比较。若某个数据和给定的值相等,则查找成功,找到所查数据的位置;反之,查找不成功。查找算法27363218d(1)d(2)d(3)d(4)输入查找的元素值key=32i=1i=2i=3此时d(i)=key,数组中的第3个位置如果输入查找的元素值key=22i=1i=2i=3i=4i=527363218d(1)d(2)d(3)d(4)此时i等于5,超过数组中元素个数,找不到从数组d的第1个元素d(1)开始,依次判断各元素的值是否与查找键key的值相等。顺序查找的流程图开始i1d(i)=key?i<=n?i i+1未找到,输出结果:0找到,输出结果:mand6_Click()'顺序查找Key=Val()Fori=1TonumIfd(i)=="在数组的"+Str(i)+"位置中"ExitForEndIfNextIfi=num+="在数组中没有找到"+Str(Key)EndIfEndSub对分查找的基本思想对分查找的前提是数据已经有序(以递增为例),然后把待查找的数据与数组中间位置的数比较,如果比中间位置的数大,在数组的后半部分继续查找,否则在数组的前半部分查找,继续对分查找,直到找到待查找的数在数组中的位置或数组已无法对分。123456789101**********下标元素M=fix((i+j)/2)=8I=1J=16第1次比较:Key>d(m)查找范围应该变成d(9)~d(16)Key=52①变量I和J记录所要查找范围的起始和终止位置过程:10151718222735454852656772859798123456789101**********下标元素10151718222735454852656772859798J=16M=fix((i+j)/2)=12第2次比较:Key<d(m)查找范围应该变成d(9)~d(11)123456789101**********下标元素10151718222735454852656772859798I=9J=11M=fix((i+j)/2)=10第3次比较:Key=d(m)找到了!②计算中间点M的位置:M=fix((i+j)/2)或M=(i+j)\2③比较key和d(M)的值,根据结果重新确定查找的起始和终止位置或者直接告诉已经找到J不变,I=M+1=9I=9I不变,J=M-1=11在规模为n的数组变量d中进行对分查找的流程图未找到,输出结果:0开始I←1,j←ni<=j?找到,输出结果:m结束NY计算中点m←(i+j)\2d(m)=key?D(m)<key?i←m+1j←m-1YYNN