查找算法课件VIP免费

查找算法顺序查找对分查找查找是一种查询数据的技术，其目标是能以比较少的步聚和较短的时间找到所需的对象。顺序查找的基本思想是从第一个数据开始，按数据的顺序逐个将数据与给定的值进行比较。若某个数据和给定的值相等，则查找成功，找到所查数据的位置；反之，查找不成功。查找算法顺序查找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?ii+1未找到，输出结果：0找到，输出结果：i结束YNYN转化成程序Key=Val(Text1.Text)Fori=1TonIfd(i)=KeyThenLabel1.Caption="在数组的"+Str(i)+"位置中"ExitForEndIfNextiIfi=n+1ThenLabel1.Caption="在数组中没有找到"+Str(Key)EndIf1、从数组的第1个元素开始，不断判断d(i)是否等于key2、最少查找1次，最多查找n次3、查找成功，输出该元素的下标i查找不成功，输出“未找到”在d(n)中用顺序查找方法查找某个值的规律：思考1：如何在最短时间猜中1000以内数字？每次猜中间数字！对分查找的基本思想对分查找的前提是数据已经有序（以递增为例），然后把待查找的数据与数组中间位置的数比较，如果比中间位置的数大，在数组的后半部分继续查找，否则在数组的前半部分查找，继续对分查找，直到找到待查找的数在数组中的位置或数组已无法对分。对分查找算法12345678910111213141516下标元素M=fix((i+j)/2)=8I=1J=16第1次比较：Key>d(m)查找范围应该变成d(9)~d(16)Key=52①变量I和J记录所要查找范围的起始和终止位置过程：1015171822273545485265677285979812345678910111213141516下标元素10151718222735454852656772859798J=16M=fix((i+j)/2)=12第2次比较：KeyKeyThenIfKeyjThenPrint“0”转化成程序练习题1、数据320,340,347,349,362,382,423,454，使用对分查找，设定查找键key，若第一个被访问到的数据是349，小于key值，则第二个被访问到的数据是（）A.340B.382C.423D.4542、7位学员的身高(单位:cm)从高到低依次为：178,177,175,172,170,165,162，用对分查找法找到178的过程中，依次被访问到的数据是（）A.178B.172,175,178C.172,177,178D.172,175,177,178比较顺序查找是一种基本、简单的查找算法，但查找的效率往往过低；对分查找时每次都把查找范围缩小一半对分查找算法数据次数较少，效率较高，但它要求数组中的数据是有序的。顺序查找与对分查找比较是否需要事先排序平均查找次数顺序查找不需要(n+1)/2多对分查找需要Log2n少