5.4 数据查找　课件-2022—2023学年浙教版（2019）高中信息技术选修1

思考 生活中的查找 1、如何在一堆试卷中查找到自己的那一张试卷？ 2、如何从一本相册中查找到自己所需的那一张？ 3、如何在一车的旅客中查找到携带违禁品的旅客？ 1 CHZX 5.4 数据查找 浙江省高中信息技术 选择性必修一 《数据与数据结构》 昌化中学 应彤鑫 2 顺序查找 算法思想 程序实现 01 3 顺序查找 Shunxu chazhao 算法思想 从第一个数据开始，按数据的顺序逐个将数据与给定的值进行比较。若某个数据与给定值相等，则查找成功，记录所查数据的位置；反之，则查找不成功。 ①算法简单，对数据是否有序没有要求。 ②查找效率较低，当数据量大时不宜使用。 算法特点 4 顺序查找 Shunxu chazhao 算法演算 d[0] d[1] d[2] d[3] d[4] d[5] 43 56 23 15 50 78 在数组序列d=[43,56,23,15,50,78]中，查找关键字key为15的元素 key=15 ①i=0，d[0]=43 !=key ②i=1，d[1]=56 !=key ③i=2，d[2]=23 !=key ④i=3，d[3]=15 ==key→查找成功 问题： 若要查找的内容在n个数据中，则最理想情况是比较_______次？最差的情况需要比较________次？ 1 n 5 顺序查找 Shunxu chazhao 算法演算 d[0] d[1] d[2] d[3] d[4] d[5] 43 56 23 15 50 78 在数组序列d=[43,56,23,15,50,78]中，查找关键字key为80的元素 key=80 ①i=0，d[0]=43 !=key ②i=1，d[1]=56 !=key …… ⑥i=5，d[5]=78 !=key 问题： 若要查找的内容不在n个数据中，则当i=________时，需反馈查找失败？ n d[6] ⑦i=6，查找失败 6 顺序查找 Shunxu chazhao 程序实现 For i in range(___________): If : ________________ else: __________________ 0,n d[i]==key print(i) print(“没找到”) ①从0到n-1逐一比较 ②如果找到，输出下标 ③若找不到，提示失败 问题： 若找到元素，后续的比较是否还有必要进行？（假设就一个元素符合条件） break 7 顺序查找 Shunxu chazhao 程序实现 Flag=False for i in range(0，n): if d[i]==key: flag=Ture break if flag: print(i) else: print(“没找到”) 找到/找不到，两种状态，利用一个逻辑型的变量flag来表示是否找到，没找到(False)继续找，找到了(True)就结束。 8 练一练 1、顺序查找算法的部分代码如下： Flag=False i=0 while i<5 and Flag==False: i=i+1 if a[i]==key : Flag=True if Flag==False : i=0 数组元素a=[8,7,3,5,4]，若key值为3，则运行该程序后，变量i的值是（ ） A.0 B.2 C.3 D.5 B 9 练一练 2、某查找算法的VB代码如下： k=0 i=0 while i<=6: if a[i]==key : k=i i=i+1 数组元素a=[5,3,5,1,8,5,9]，当变量key值为5时，运用该算法处理后，变量k的值是( ) A.1 B.2 C.5 D.0 C 10 练一练 3.某查找算法的VB代码如下： k=0 i=0 while i<=6: if a[i]==key : k=i break i=i+1 数组元素a=[5,3,5,1,8,5,9]，当变量key值为5时，运用该算法处理后，变量k的值是( ) A.1 B.2 C.5 D.0 D 11 思考 现有1~100共100个数字，且这100个数字按顺序升序排列，待查找数key是这其中的一个，如何快速找到这个key？ 12 对分查找 算法思想 程序实现 02 13 对分查找 Duifen chazhao 算法思想 首先将查找的数与有序数组内处