高中信息技术浙教版 (2019)选修1 数据与数据结构5.4 数据查找多媒体教学ppt课件

这是一份高中信息技术浙教版 (2019)选修1 数据与数据结构5.4 数据查找多媒体教学ppt课件，共28页。PPT课件主要包含了查找动物问题，猜数字游戏，抽象与建模，设计算法与数据结构，程序实现等内容，欢迎下载使用。

请在扑克牌中寻找出下面这张牌，讲一讲你寻找的方法
生活中还有哪些查找的具体例子，你是通过什么样的方法快速进行查找的。
查找（Search）又称检索，是计算机根据所给条件查找出满足条件的对象，即在存储的一批数据内寻找出一个特定的数据，或者确定在该批数据内是否存在这样的数据。
②输入查找关键值key；
③从数组中的第一个元素开始与关键值key进行比较，若相等，则输出相应信息；否则，继续比较下一个元素。
①将待查找的数据储存在数组中；
④直到找完数组的最后一个元素仍不想等，输出查找失败。
A数组中存放了一些动物名称“dg” “cat” “mnkey” “tiger” “panda” “rabbit” “hrse”，现在想查找动物“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]比较，结果必然是如下三种情况之一：
keykey=d[m] 找到了需要的数据。
key>d[m] 数组d递增，新的查找范围为（m+1，j）。
思考：若数组d递减，查找范围（i,j）如何变化？
key=12查找过程：
中点位置m的计算？i、j的变化规律？
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 = 0j = len(d)-1while i <= j: m = (i+j) //2 if d[m] == key: f=True b=m break if key < d[m]: # 到左边去找 j = m-1 else: # 到右边去找 i = m + 1if f==True: print("查找成功！第"+str(b)+"个")else:print("没有找到！")
二分查找延伸——二叉树
从根结点到待查结点的一条路径为25→15→6→12，比较次数为4次。通过观察可知，在n个元素排序的顺序表里，某一次查找过程中，所做比较次数不超过判定树的高度加1，即
1. 二分查找算法的基本思想，顺序查找和二分查找的区别；2. 二分查找算法的特点及适用范围；3. 二分查找的基本方法，确定查找区间中点m的位置； 4. 查找键key值与d[m]比较的三种情况。
航空公司VIP会员积分查询部分数据（Excel数据）
问题：从表中的数据可以看出，每个会员的信息是一条记录，包括VIP号、姓名、飞行里程、积分等数据项。根据刚才的实践体验，对记录快速查询会员积分，查找应当如何进行？
数据查找算法有两种，哪种更适合？
查找可采用顺序查找算法或二分查找算法，对数据进行一次查找，采用顺序查找算法。对数据重复查找，二分查找算法的效率高于顺序查找算法，但二分查找提前：被查找的数据序列必须是有序，即在查找前要按VIP号为关键字进行排序。