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

4.3查找算法设计顺序查找和对半查找查找是一种查询数据的技术，其目标是能以比较少的步聚和较短的时间找到所需的对象。顺序查找的基本思想是从第一个数据开始，按数据的顺序逐个将数据与给定的值进行比较。若某个数据和给定的值相等，则查找成功，找到所查数据的位置；反之，查找不成功。查找算法顺序查找27363218d(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次比较：Key>d(m)查找范围应该变成d(9)~d(16)Key=52我们用变量I和J记录所要查找范围的起始和终止位置（1）过程：1015171822273545485265677285979812345678910111213141516下标元素数组d():I=9J=16M=fix((i+j)/2)=12第2次比较：Key<d(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<=j

Ifd(M)=KeyThenLabel6.Caption="在数组的"+Str(M)+"位置中"

ExitSubEndIfIfd(M)<KeyThen

ElseEndIfLoopLabel6.Caption="在数组中没有找到"+Str(Key)m=(i+j)\2i=m+1j=m-1比较顺序查找是一种基本、简单的查找算法，但查找的效率往往过低；对分查找时每次都把查