查找算法课件.ppt

1、顺序查找和对分查找,查找算法,查找是一种查询数据的技术，其目标是能以比较少的步聚和较短的时间找到所需的对象。,顺序查找的基本思想 是从第一个数据开始，按数据的顺序逐个将数据与给定的值进行比较。若某个数据和给定的值相等，则查找成功，找到所查数据的位置；反之，查找不成功。,查找算法,顺序查找,输入查找的元素值key=32,此时d(i)=key,数组中的第3个位置,如果输入查找的元素值key=22,此时i等于5,超过数组中元素个数,找不到,从数组d的第1个元素d(1)开始，依次判断各元素的值是否与查找键key的值相等。,顺序查找的流程图,程序实现,Private Sub Command6_Click

2、() 顺序查找 Key = Val(Text2.Text) For i = 1 To num If d(i) = Key Then Label5.Caption = 在数组的 + Str(i) + 位置中 Exit For End If Next If i = num + 1 Then Label5.Caption = 在数组中没有找到 + Str(Key) End If End Sub,对分查找的基本思想 对分查找的前提是数据已经有序（以递增为例），然后把待查找的数据与数组中间位置的数比较，如果比中间位置的数大，在数组的后半部分继续查找，否则在数组的前半部分查找，继续对分查找，直到找到待查找

3、的数在数组中的位置或数组已无法对分。,第1次比较： Keyd(m) 查找范围应该 变成d(9)d(16),Key=52,变量 I和J记录所要查找范围的起始和终止位置,过程：,第2次比较： Keyd(m) 查找范围应该 变成d(9)d(11),第3次比较： Key=d(m) 找到了！,计算中间点M的位置：M=fix(i+j)/2) 或M= (i+j)2,比较key和d(M)的值，根据结果重新确定查找的起始和终止位置或者直接告诉已经找到,J不变，I=M+1=9,I不变，J=M-1=11,顺序查找的流程图,程序实现,Private Sub Command6_Click() 顺序查找 Key = Va

4、l(Text2.Text) For i = 1 To num If d(i) = Key Then Label5.Caption = 在数组的 + Str(i) + 位置中 Exit For End If Next If i = num + 1 Then Label5.Caption = 在数组中没有找到 + Str(Key) End If End Sub,自然语言描述对分查找： 1、（确定初始查找范围）i1,jn 2、（是否继续查找？）如果i=j,那么转到4 3、（找不到）输出结果，算法结束 4、（计算中点位置）m(i+j2) 5、（相等？）d(m)=key,那么转到7 6、（修改查找范围）

5、如果keyd(m)那么jm-1,否则im+1,转到2 7、（找到）输出结果m，算法结束,代码分析command4的click过程,Key = Val(Text2.Text) i = 1 j = num Do While i = j If d(M) = Key Then Label6.Caption = 在数组的 + Str(M) + 位置中 Exit Sub End If If d(M) Key Then Else End If Loop Label6.Caption = 在数组中没有找到 + Str(Key),m = fix(i + j) / 2 ) 或 m= ( i + j ) 2,i =

6、 m + 1,j= m - 1,比较,顺序查找是一种基本、简单的查找算法，但查找的效率往往过低； 对分查找时每次都把查找范围缩小一半,经过k次比较，剩下的查找范围数据个数不超过n/2k 对分查找算法数据次数较少，效率较高，但它要求数组中的数据是有序的。,顺序查找与对分查找比较,课堂练习,1.一个数组中含有元素A、B、C、D、E、F、G、H、I、J、K、L、M、N应用对分查找算法，查找目标为J时，会查经哪几个字母，如果查找的是Z呢？ 2.数组元素为：Alice、Byron、Duane、Elaine、Floyd、Gene、Herry、Iris，请回答： 哪个查找算法（顺序查找和对分查找）能比较快找

7、到名字Gene? 哪个查找算法（顺序查找和对分查找）能比较快地测定名字Sue不存在? 当利用顺序查找算法查找名字Floyd时，查问了多少个数据？使用对分查找算法时，又要查问多少个数据？,查找J时，会查经H、L，查找Z，会查经H、L、N，最后查找z未找到,对分查找快，对分查找3次，顺序查找6次,对分查找快，对分查找4次，顺序查找8次,使用顺序查找Floyd，查找了5个数据，使用对分查找，查问了1个数据,课堂练习,3.进行对分查找算法的前提是: (A)被查找数据元素个数是奇数 (B)被查找数据元素个数是偶数 (C)被查找数据元素是有序的 (D)被查找数据元素是无序的4.用对分查找法从数列3，6，7

8、，10，12，16，25，30，75中找到数据10的最少查找次数是: (A) 2 (B) 3 (C) 4 (D) 7 5.应用对分查找算法查找一个有200个表项的列表时，必须查问的表项数目至多有几个？如果列表中有10万个表项又怎样？ 6.某大学的学生数据库中，包含有3万条学生记录。如果取出一条记录，再与指定学号进行比较，总共需要花10毫秒。 （1）如果采用顺序查找，平均说来查找一条学生记录需要花多少时间？ （2）如果采用对分查找，最多只要检查多少个表项，就能找到目标记录？找一条目标记录的过程只要花多少时间？,C,c,8 / 17,150S,15个，0.15s,课堂练习,7.验血问题的算法。有万大军三天后将要出发作战。军医发现有一位士兵带入了一种传染病菌，三天后发作将传染给全军，使部队丧失作战能力，只有通过验血才能发现谁是患者。但当时军医每天至多只能检验份血样，如果逐一地进行化验需要天，这将贻误战机。要求设计一个算法，帮助军医解决上述问题。,算法如下： 第一天，将10万人分成100组，每组1000人，滴血于一处，成为一份血样，总共有100份血样，对这100份血样进行验血，查出带菌血样所在组A； 第二天，将有带菌血样所在组A的1000人分成100组，每组10