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