数据查找--浙教版（2019）高中信息技术选修1.pptx

《数据查找--浙教版（2019）高中信息技术选修1.pptx》由会员分享，可在线阅读，更多相关《数据查找--浙教版（2019）高中信息技术选修1.pptx（27页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、思考思考u生活中的查找1、如何在一堆试卷中查找到自己的那一张试卷？2、如何从一本相册中查找到自己所需的那一张？3、如何在一车的旅客中查找到携带违禁品的旅客？5.4 数据查找浙江省高中信息技术 选择性必修一 数据与数据结构昌化中学 应彤 鑫顺序序查找找算法思想程序实现顺 序 查 找S h u n x u c h a z h a oS h u n x u c h a z h a o算法思想从第一个数据开始，按数据的顺序逐个将数据与给定的值进行比较。若某个数据与给定值相等，则查找成功，记录所查数据的位置；反之，则查找不成功。算法简单，对数据是否有序没有要求。查找效率较低，当数据量大时不宜使用。算法特

2、点顺 序 查 找S h u n x u c h a z h a oS h u n x u c h a z h a o算法演算d0d1d2d3d4d5435623155078在数组序列d=43,56,23,15,50,78中，查找关键字key为15的元素key=15i=0，d0=43 !=keyi=1，d1=56 !=keyi=2，d2=23 !=keyi=3，d3=15 =key查找成功问题：若要查找的内容在n个数据中，则最理想情况是比较_次？最差的情况需要比较_次？1n顺 序 查 找S h u n x u c h a z h a oS h u n x u c h a z h a o算法演算d

3、0d1d2d3d4d5435623155078在数组序列d=43,56,23,15,50,78中，查找关键字key为80的元素key=80i=0，d0=43 !=keyi=1，d1=56 !=keyi=5，d5=78 !=key问题：若要查找的内容不在n个数据中，则当i=_时，需反馈查找失败？nd6i=6，查找失败顺 序 查 找S h u n x u c h a z h a oS h u n x u c h a z h a o程序实现For i in range(_):If :_ else:_0,ndi=keyprint(i)print(“没找到”)从0到n-1逐一比较如果找到，输出下标若找不

4、到，提示失败问题：若找到元素，后续的比较是否还有必要进行？（假设就一个元素符合条件）break顺 序 查 找S h u n x u c h a z h a oS h u n x u c h a z h a o程序实现Flag=Falsefor i in range(0，n):if di=key:flag=Ture breakif flag:print(i)else:print(“没找到”)找到/找不到，两种状态，利用一个逻辑型的变量flag来表示是否找到，没找到(False)继续找，找到了(True)就结束。练一练1、顺序查找算法的部分代码如下：Flag=Falsei=0while i5 an

5、d Flag=False:i=i+1 if ai=key:Flag=Trueif Flag=False:i=0数组元素a=8,7,3,5,4，若key值为3，则运行该程序后，变量i的值是（）A.0 B.2 C.3 D.5B练一练2、某查找算法的VB代码如下：k=0i=0while i=6:if ai=key:k=i i=i+1数组元素a=5,3,5,1,8,5,9，当变量key值为5时，运用该算法处理后，变量k的值是()A.1B.2C.5D.0C练一练3.某查找算法的VB代码如下：k=0i=0while i=6:if ai=key:k=i break i=i+1数组元素a=5,3,5,1,8,

6、5,9，当变量key值为5时，运用该算法处理后，变量k的值是()A.1B.2C.5D.0D思考思考现有1100共100个数字，且这100个数字按顺序升序排列，待查找数key是这其中的一个，如何快速找到这个key？对分分查找找算法思想程序实现对 分 查 找D u i f e n c h a z h a oD u i f e n c h a z h a o算法思想首先将查找的数与有序数组内处于中间位置的数据比较，如果中间位置上的数与查找的数不同，则根据有序性，确定应该在数组的前半部分还是后半部分继续查找。在新确定的范围内，继续按上述方法，直到获得最终结果。要求被查找数据必须有序。查找效率非常高，适

7、用于大数据查找。算法特点对 分 查 找D u i f e n c h a z h a oD u i f e n c h a z h a o算法演算用数组d存放数组序列，用i表示查找范围的第一个数组元素下标，用j表示最后一个数组元素下标。假如查找键key=48？d0d1d2d3d4d5d6d7d8d9ijmid第1次查找：范围为_，i=_，j=_，mid=_。dmid=_。dmid_key？后续查找的范围应该是_。d0d909(0+9)/2=4d4=22d5d9对 分 查 找D u i f e n c h a z h a oD u i f e n c h a z h a o算法演算用数组d存放数

8、组序列，用i表示查找范围的第一个数组元素下标，用j表示最后一个数组元素下标。假如查找键key=48？d5d6d7d8d9ijmid第2次查找：范围为_，i=_，j=_，mid=_ 。d(mid)=_。d(mid)_key？后续查找的范围应该是_。d5d995(5+9)/2=745d8d9d0d1d2d3d4d5d6d7d8d9ijmid对 分 查 找D u i f e n c h a z h a oD u i f e n c h a z h a o算法演算用数组d存放数组序列，用i表示查找范围的第一个数组元素下标，用j表示最后一个数组元素下标。假如查找键key=48？d5d6d7d8d9ijm

9、idd0d1d2d3d4d5d6d7d8d9ijmid4852d8d9ijmid第3次查找：范围为_，i=_，j=_，mid=_。d(mid)=_。d(mid)_key？d8d989(8+9)/2=848=提示查找成功对 分 查 找D u i f e n c h a z h a oD u i f e n c h a z h a o算法演算用数组d存放数组序列，用i表示查找范围的第一个数组元素下标，用j表示最后一个数组元素下标。假如查找键key=48？d0d1d2d3d4d5d6d7d8d9第一次查找：d0d9，i=0，j=9，mid=4，dmidkey第二次查找：d5d9，i=5，j=9，mi

10、d=7，dmidkey第三次查找：d8d9，i=8，j=9，mid=8，dmid=key思考若dmidkey第二次查找：d(1)d(4)，i=1，j=4，mid=2，d(mid)key，则新查找的范围为_部分（前半/后半）若d(mid)key,i和j是如何变化的？前半i不变，j=mid-1对 分 查 找D u i f e n c h a z h a oD u i f e n c h a z h a o算法演算用数组d存放数组序列，用i表示查找范围的第一个数组元素下标，用j表示最后一个数组元素下标。假如查找键key=20？d0d1d2d3d4d5d6d7d8d910151718d0d1d2d3i

11、jmid1718d2d3ijmid18d3i,j,mid思考继续进行查找的条件是什么？在什么情况下查找会结束？当ij时，找不到数据，查找结束。ijmid对 分 查 找D u i f e n c h a z h a oD u i f e n c h a z h a o算法演算数组a0a1a2a3a4a5a6a7a8a9值291115182629303849查找次数3143234324对分查找的查找效率10个数进行对分查找算法，则平均查找次数：次。对分查找最多查找次数：次。2.9Log2n+1对 分 查 找D u i f e n c h a z h a oD u i f e n c h a z h

12、 a o算法演算（1）key与dmid的大小比较影响i，j在后续查找中的取值。若dmidkey，则j=mid-1，i不变（2）继续重复进行查找的条件。当i=j时（3）对分查找最多的查找次数(n个数据)。最多次数=Int(log2n)+1n个数据对分x次最后变为1个数据n*(1/2)x=1x=log2n最后一个数据还要参与一次查找最多次数=Int(log2n)+1练一练1.用对分查找从数列3、6、7、10、12、16、25、30、75中查找数据10，则依次访问的数据为()A.12、6、7、10B.12、7、10C.12、6、10 D.12、7、6、10A数组a0a1a2a3a4a5a6a7a8值

13、367101216253075m1m2m3m4对 分 查 找D u i f e n c h a z h a oD u i f e n c h a z h a o算法演算开始i=0,j=9dmid=key?dmidkey?查找成功查找失败结束YNYNYNmid=ikey:else:if f=True:print(查找成功！下标为+str(m)else:print(没有找到！)i=j(i+j)/2j=m-1i=m+1给i,j赋初值，当i=j时，重复执行查找工作对分，取中值m判断中值是否就是查找键如果中值不是查找键，则判定下一个查找范围应该在前半部分还是在后半部分。注意i和j的控制。输出查找结果len(d)-1练一练1.某二分查找算法的程序如下：i0j7 n0while i dm：jm1 else：im1 数组元素d0到d7的值依次为83，75，62，41，33，27，16，2，若运行该程序段后，n的值为2，则key的值可能是()A.62或16 B.62或27 C.75或27 D.75或16C练一练