《查找算法设计》教学课件2.pptVIP

4.3查找算法设计顺序查找和对半查找

查找是一种查询数据的技术，其目标是能以比较少的步聚和较短的时间找到所需的对象。顺序查找的基本思想是从第一个数据开始，按数据的顺序逐个将数据与给定的值进行比较。若某个数据和给定的值相等，则查找成功，找到所查数据的位置；反之，查找不成功。查找算法

顺序查(1)d(2)d(3)d(4)输入查找的元素值key=32i=1i=2i=3此时d(i)=key,数组中的第3个位置从数组d的第1个元素d(1)开始，依次判断各元素的值是否与查找键key的值相等。

顺序查找如果输入查找的元素值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?ii+1未找到，输出结果：0找到，输出结果：i结束YNYN

转化成程序PrivateSubCommand6_Click()顺序查找Key=Val(Text2.Text)Fori=1TonumIfd(i)=KeyThenLabel5.Caption=在数组的+Str(i)+位置中ExitForEndIfNextIfi=num+1ThenLabel5.Caption=在数组中没有找到+Str(Key)EndIfEndSub

对半查找的基本思想对半查找的前提是数据已经有序（以递增为例），然后把待查找的数据与数组中间位置的数比较，如果比中间位置的数大，在数组的后半部分继续查找，否则在数组的前半部分查找，继续对分查找，直到找到待查找的数在数组中的位置或数组已无法对分。

1015171822273545485265677285979812345678910111213141516下标元素数组d(i):I=1J=16M=fix((i+j)/2)=8第1次比较：Keyd(m)查找范围应该变成d(9)~d(16)Key=52我们用变量I和J记录所要查找范围的起始和终止位置（1）过程：

1015171822273545485265677285979812345678910111213141516下标元素数组d():I=9J=16M=fix((i+j)/2)=12第2次比较：Keyd(m)查找范围应该变成d(9)~d(11)Key=52我们用变量I和J记录所要查找范围的起始和终止位置

1015171822273545485265677285979812345678910111213141516下标元素I=9J=11M=fix((i+j)/2)=10第3次比较：Key=d(m)找到了Key=52

在规模为n的数组变量d中进行对分查找的流程图未找到，输出结果：0开始I←1，j←ni=j?找到，输出结果：m结束NY计算中点m←(i+j)\2d(m)=key?D(m)key?i←m+1j←m-1YYNN

代码分析command4的click过程Key=Val(Text2.Text)i=1j=numDoWhilei=jIfd(M)=KeyThenLabel6.Caption=在数组的+Str(M)+位置中ExitSubEndIfIfd(M)KeyThenElseEndIfLoopLabel6.Caption=在数组中没有找到+Str(Key)m=(i+j)\2i=m+1j=m-1

比较顺序查找是一种基本、简单的查找算法，但查找的效率往往过低；对分查找时每次都把查找范围缩小一半对分查找算法数据次数较少，效率较高，但它要求数组中的数据是有序的。

顺序查找与对半查找比较是否需要事先排序平均查找次数顺序查找不需要(n+1)/2多对分查找需要Log2n少