5.4 数据查找 课件（28张PPT）

(课件网) 选择性必修模块1《数据与数据结构》 第五章 数据结构与算法 5.4. 数据查找 新扑克牌 打乱后的扑克牌 情境导入 请在扑克牌中寻找出下面这张牌，讲一讲你寻找的方法 思考： 生活中还有哪些查找的具体例子，你是通过什么样的方法快速进行查找的。 查找（Search）又称检索，是计算机根据所给条件查找出满足条件的对象，即在存储的一批数据内寻找出一个特定的数据，或者确定在该批数据内是否存在这样的数据。 算法 思想 ②输入查找关键值key； ③从数组中的第一个元素开始与关键值key进行比较，若相等，则输出相应信息；否则，继续比较下一个元素。 ①将待查找的数据储存在数组中； ④直到找完数组的最后一个元素仍不想等，输出查找失败。 顺序查找算法思想 查找动物问题 A数组中存放了一些动物名称“dog” “cat” “monkey” “tiger” “panda” “rabbit” “horse”，现在想查找动物“bear”是否在其中，如找到输出“查找成功！是第几个动物”，否则输出“查找失败”，无论查找成功与否都输出比较的次数。 返回 拓展提升 某个班级的部分学生语文成绩如下表所示，要求实现根据考号查询该生的语文成绩，如查询不到则显示“该班无此学生”。 思考： 用哪一种数据结构对表格数据进行存储？ 对哪个字段进行顺序查找？ 思考： 若一个班级一共有45人，查找成功最好情况是比较几次？最差呢？若查找不成功，需要比较几次？ 若有N个数据，那顺序查找的平均比较次数为几次？ 若一个数据序列有n个数，查找不成功的比较次数为n，查找成功：最好的情况为1次，最差的情况为n次，所以查找成功时的平均比较次数为(n+1)/2，且顺序查找的时间复杂度为O(n) 情境导入 猜数字游戏 观看视频，思考： 生活中“如何迅速的找到东西”？ 二分查找 二分查找（binary search）又称折半查找，对分查找。 它是一种效率很高的查找方法，但被查找的数据序列必须是有序的。 算法 思想 ②如果中间位置上的元素内的数值与查找键不同，根据数组元素的有序性，就可确定应该在数组的前半部分还是后半部分继续进行查找 ③在新确定的范围内，继续按上述方法进行查找，直到获得最终结果。 ①将查找键与有序数组内处于中间位置的元素进行比较； 二分查找算法思想 实践体验： 在数组d的11个元素中，已按增序存储了11个数据：6、12、15、18、22、25、28、35、46、58、60，如何用二分法查找数据12（已存储在变量key中）？ 提示： 11个数据存储在d[0]到d[10] Key=12 思考： 如何确定查找区间中点m的位置？ 讨论： 查找范围（i,j）的变化情况？ 将查找键key值与d[m]比较，结果必然是如下三种情况之一： keyd[m] 数组d递增，新的查找范围为（m+1，j）。 思考：若数组d递减，查找范围（i,j）如何变化？ 情境导入 key=12 查找过程： 6 12 15 18 22 25 28 35 46 58 60 0 1 2 3 4 5 6 7 8 9 10 中点位置m的计算？ i、j的变化规律？ 二分查找规律 中点位置 m= keyd[m] 由于与①相同的理由，必须在新的范围（m+1，j）中继续查找。 这样，除了出现情况②，在通过一次比较后，新的查找范围将不超过上一次查找范围的一半。 查找键key值与d[m]比较结果情况总结： 二分查找流程图 二分查找程序实现 d=[6,12,15,18,22,25,28,35,46,58,60] f=False # i和j定义子数组的边界，一开始搜索的是整个数组 i = 0 j = len(d)-1 while i <= j: m = (i+j) //2 if d ... ...