第4节-查找算法及程序实现课件

,总纲目录,教材研读,重难突破,栏目索引,第,4,节,查找算法及程序实现,第4节-查找算法及程序实现课件,1,一,查找算法的基本思想,二,查找算法的程序实现,教材,研读,一查找算法的基本思想二查找算法的程序实现教材研读,突破,对分查找,重难突破,突破 对分查找重难突破,一、查找算法的基本思想,1.顺序查找,顺序查找的基本思想是从第一个数据开始,按数据的顺序逐个将数,据与给定的值进行比较。若某个数据和给定值相等,则查找成功;如果所,有的数据都比较过,没有一个数据和给定值相等,则查找不成功。,教材研读,一、查找算法的基本思想教材研读,4,2.对分查找,对分查找的基本思想是在有序的数据列中,首先将要查找的数据与有,序数组内处于中间位置的数据进行比较,如果两者相等,则查找成功;否则,根据数组元素的有序性,就可确定该数据应该在数组的前半部分还是后,半部分继续进行查找。在新确定的范围内,继续按上述方法进行查找,直到找到要查找的数据,则查找成功,或直到子表不存在,则查找不成功。,对分查找的条件是被查找的数据列必须是有序的。,2.对分查找,5,二、查找算法的程序实现,1.顺序查找,在数据源中从头到尾逐个与查找关键词比较,顺序查找的代码如下:,For i=1 To n,If a(i)=key Then,Print i:Exit For,End If,Next i,If i=n+1 then s=“未找到”,二、查找算法的程序实现1.顺序查找,6,说明:for 语句用于访问整个查找源的数据,一般是从开始位置到结束,位置。,if 语句用于判断当前访问的元素是不是等于关键词。,一旦某个位置的数据等于关键词,则输出该位置,并且查找任务结束,通常用语句 Exit for 退出循环。,未找到,也应该有输出。能找到的情况下,因为是通过exit for退出循,环的,因此退出循环时i=n;找不到的情况下,退出循环时i=n+1。,顺序查找不要求数据源是有序的。,说明:for 语句用于访问整个查找源的数据,一般是从开始位,7,2.,对分查找的代码如下:,key=text1.text,􀆳,输入关键词,i=1:j=n,􀆳,设置首次查找的范围,f=False,􀆳,f标志是否已经找到关键词,Do While i=j And Not f,􀆳,未找到并且查找范围还存在,m=(i+j)2,􀆳,计算中间位置,If key=a(m) Then,f=True,􀆳,相等表示找到了,将f设为True,2.对分查找的代码如下:,8,ElseIf keya(m) Then,j=m-1,􀆳,下一次查找范围是前半部分,Else,i=m+1,􀆳,下一次查找范围是后半部分,End If,Loop,ElseIf keya(m) Then,9,说明:,变量 i 和 j 记录每一次查找的起始位置和结束位置,变量 m,记录中间位置。如果 keya(m),则下一次查找的范围是后半部分,因此 j 不,变,i=m+1。,退出 DO 循环有两种可能:第一种是 f 为 True,说明已经找到关键词,此时结束查找;第二种是 ij,查找的起始位置超过结束位置,说明已经找,遍数据源,但是找不到关键词,此时结束查找。,对分查找的前提是被查找的数据必须是有序的。,说明:变量 i 和 j 记录每一次查找的起始位置,10,3.对分查找的其他写法,key=text1.text,i=1:j=n,Do Whilei=j,m=(i+j)2,If key=a(m) Then Exit Do,􀆳,找到关键词,直接退出循环,If key172,因此下一次查找的范围是前半部分,即第1个到第,3个。因此第二次访问的数据应该是第2个,即177(中间位置m=Fix(1+,3)/2)=2),178177,因此下一次查找的范围是前半部分,即第1个,因此第,三次访问的数据是第1个,即178。,解析本题主要考查对对分查找算法基本思想的理解。将7个数据,18,5.,有一组数据为“2、3、5、5、7、7、8”,利用顺序查找和对分查找,查找5时,则分别查找几次可以找到目标值,(,C,),A.3无法使用对分查找B.4无法使用对分查找,C.31 D.41,5.有一组数据为“2、3、5、5、7、7、8”,利用顺序查找,19,解析,本题主要考查顺序查找和对分查找的基本思想。顺序查找,的基本思想是在数据源中从头到尾逐个与查找关键词比较,因此顺序查,找第3次查找找到目标值5。对分查找的基本思想是将查找关键词与数,据源中间位置的数据进行比较,如果两者相等,则查找成功;如果不相等,则将查找范围缩小一半,并进行下一次查找。数据源中间位置的数据是,5,因此第1次查找就找到了目标。,解析本题主要考查顺序查找和对分查找的基本思想。顺序查找的,20,6.,数组A中存放了某校学生的身高数据(单位:厘米),数据存放情况如下,表:,A(1),A(2),A(3),A(4),A(5),A(6),A(7),A(8),A(9),A(10),A(11),185,182,178,176,176,175,171,169,167,166,165,若要查找数组中是否存在数据182,以下表述正确的是,(,A,),A.本组数据既能采用对分查找算法,也能采用顺序查找算法,B.本组数据采用对分查找需比较4次,而顺序查找只需2次,所以对分查,找效率高的说法不对,C.本组数据须先对数据进行升序排序后才能进行对分查找,D.本组数据由于存在相同数据176,所以不能采用对分查找算法,6.数组A中存放了某校学生的身高数据(单位:厘米),数据存放,21,解析,本题主要考查查找算法的基本概念。顺序查找对于数据源,没有要求,可以是无序的,也可以是有序的,而对分查找要求数据源必须,是有序的,可以是升序的也可以是降序的,这是由顺序查找和对分查找,的思想方法决定的。从表中可以看出该组数据源是有序的,而且是降,序。因此选项A正确,C错误。如果数据源中存在相同的数据,则一般情,况下只要找到了一个,查找就算完成,因此存在相同数据时也可以使用,对分查找,D错误。顺序查找平均需要比较(n+1)/2次,因此时间复杂度是,O(n),而对分查找的每一次查找都将查找范围缩小一半,因此时间复杂,解析本题主要考查查找算法的基本概念。顺序查找对于数据源没,22,度是O(log,2,n),比顺序查找的效率高。虽然对于查找某些关键词(往往在,数据源中是比较靠前的),顺序查找很快,但这只是特殊情况,不能代表平,均情况。,度是O(log2n),比顺序查找的效率高。虽然对于查找某些关,23,对分查找,对分查找的基本思想:查找的数据源 a(1)到 a(n)是有序的(如从小,到大排序),查找的关键词是 key,则第一次查找的范围是1,n,如果中间,位置为 m,则 m=(1+n)2。如果key=a(m),则查找成功;如果 keya(m),则下一次查找的范围变,为m+1,n。在新确定的范围内,继续按上述方法进行查找,直到找到要,重难突破,对分查找重难突破,24,查找的数据,则查找成功;或直到子表不存在,则查找不成功。,说明:对分查找的每一次查找,要么找到了目标,结束任务;要么通过,比较中间值与关键词,将下一次的查找范围缩小一半,因此对分查找的效,率往往高于顺序查找。对n个数据查找某个值,最多需要查找int(log,2,n)+,1次。,找不到关键词的情况下,最后一遍查找时,i=j=m,若keya(m),则i=m+,1;若keya(m), 则j=m-1。这两种情况都得到i=j+1,起始位置超过结束位,置,则该遍查找结束后会退出循环。,查找的数据,则查找成功;或直到子表不存在,则查找不成功。,25,计算中间值位置的式子有多种写法,不同写法,查找过程可能不同。,实例:a(1)到a(10)的值依次为2,7,8, 10, 12, 13, 16, 18, 19, 20,公式,查找过程,m=(i+j)2,m=int(i+j)/2),m=fix(i+j)/2),m=int(i+j+l)/2),m=int(i+j)/2+0.5),m=(i+j)2,if(i+j) mod 2=1,then m=m+1,计算中间值位置的式子有多种写法,不同写法,查找过程,26,序号表示第几次找到该数。如果“if (i+j) mod 2=1 then m=m+1”写,成“if j mod 2=0 then m=m+1”,查找过程可能也不同,要根据实际情况。,序号表示第几次找到该数。如果“if (i+j) mod,27,例1,有一个由4000个整数构成的顺序表,假定表中的元素已经按升序,排列,采用对分查找查找一个元素,则最多需要,次比较就能确,定是否存在所查找的元素,(,B,),A.11B.12C.13D.14,例1有一个由4000个整数构成的顺序表,假定表中的元素已经,28,解析,本题主要考查对分查找的效率问题。根据对分查找的思想方法,每一次查找的结果要么是找到,要么是找不到,如果找不到则将下一次,的查找范围缩小一半。最差的情况是数据源中没有查找对象,每次查找,都将查找范围缩小一半。规模为n个数的数据源,使用对分查找时,最多,经过Int(log,2,n)+1次查找。Int(log,2,4000)+1=11+1=12。,解析本题主要考查对分查找的效率问题。根据对分查找的思想方法,29,例2,某对分査找算法的VB程序段如下:,i=1: j=10: s=,Key=Val(Text1.Text),Do While i =j,m=Int(i+j+1) / 2),s=s+Str(m),If Key=a(m) Then Exit Do,Exit Do 表示退出循环,例2某对分査找算法的VB程序段如下:,30,ElseIf Key a(m) Then,j=m-1,Else,i=m+1,End If,Loop,Text2.Text=s,数组元素a(1)到a(10)的值依次为“3,10,25,34,40,52,61,72,83,90”。该,ElseIf Key a(m) Then,31,程序段执行后,下列说法中正确的是,(,D,),A.待查找的数据只能是整数,B.在文本框Text1中输入任意正整数进行查找,则查找的次数介于1和5,之间,C.在文本框Text1中输入10,则文本框Text2中显示的内容为5 2,D.若在某次查找中,i=j时,条件“Key=a(m)”仍不成立,表示查找的数据,不存在,程序段执行后,下列说法中正确的是(D),32,解析,本题属于较难题,考查对分查找算法的思路。本题要点在于对分,查找各种情况的判断,由程序可知,Key为待查找数据,其值可以是任意,数,查找的最多次数为Int(log,2,10+1)=4次,当Key=10时,依次访问的位置,为6、3、2,故排除A、B、C选项。当i=j时,表示访问的数据为最后一个,数据,若条件“Key=a(m)”仍不成立,则原数据序列中无该数据。,解析本题属于较难题,考查对分查找算法的思路。本题要点在于对,33,枚举算法与顺序查找,枚举算法,顺序查找,思想方法,一一列举所有可能解并验证,数据源从头到尾逐个比较,核心代码,For(列举所有可能的解),If可能解是正确解then输出该解,next,For(从数组的第一个元素到最后一个元素),If当前元素=关键词then输出该位置,next,区分方法,For语句用于列举所有可能的解,即解的范围,For语句用于访问整个查找源的数据,一般是从开始位置到结束,位置,If语句是验证当前列举的可能解是否是正确解,If语句用于判断当前访问的元素是不是等于关键词,正确解可能有多个,因此找到一个正确解后,循环继续,直到所有,可能的解都被检验过,一旦某个位置的数据等于关键词,则记录该位置,并且查找任务,结束,通常用语句exit for退出循环,易混易淆,枚举算法与顺序查找 枚举算法顺序查找思想方法一一列举所有可能,34,头到尾逐个访问数据源中的数据;if语句是检验可能解还是比较关键词。,不管是枚举算法还是顺序查找,都可以写成For循环语句,区分的方,法是要分析问题的本质:for语句是为了一一列举所有可能的解还是从,头到尾逐个访问数据源中的数据;if语句是检验可能解还是比较关,35,