5.4.1 数据查找-教学设计（表格式）

教学设计 课程基本信息 课题 数据查找 教学目标 1.通过具体实例理解查找的概念和基本方法。 2.掌握顺序查找的算法思想，熟悉顺序查找算法的代码框架。 3.理解并掌握对分查找的算法思想，熟悉对分查找算法的代码框架。 4.理解并掌握顺序查找与对分查找算法的使用条件和优缺点。 教学内容 教学重点： 1.顺序查找算法思想及程序实现。 2.对分查找算法思想及程序实现。 3.顺序查找、对分查找算法优缺点。 教学难点： 1.对分查找算法查找过程。 2.对分查找算法基本框架及程序实现。 教学过程 【创设情境】 在乱序扑克牌中寻找“红桃5”，讲一讲你的寻找方法？ 学生回答：在乱序扑克牌中，一张一张依次寻找，直到找到为止。 二、【探究学习】 查找的定义 查找（Search）又称检索，是计算机根据所给条件查找出满足条件的对象，即在存储的一批数据内寻找出一个特定的数据，或者确定在该批数据内是否存在这样的数据。 常用查找算法：顺序查找、对分查找。 顺序查找算法基本思想 顺序查找又称线性查找，从顺序表的一端开始，依次将每个元素的关键字与给定值key（查找键）进行比较。若某个元素的关键字等于key，则表明查找成功；若所有元素都比较完毕仍找不到，则表明查找失败。 ”乱序扑克牌查找“———顺序查找自然语言描述： 问题描述：在不考虑扑克牌花色的情况下，仅在A到K,13张扑克牌中寻找指定的牌。扑克牌2～ 10 为数字本身,A 为 1 ,J 为 11 ,Q 为 12 ,K 为 13，变量Key存储要查找的牌。 第一步：将代表13张扑克牌对应的数字存储于数组d中， 要查找的扑克牌对应数字储于变量key中。 第二步：依次将d数组中元素与key进行比较。 第三：若数组中某个数与key相等则查找成功,若所有元素比较完毕仍找不到，则查找失败。 提问：上述算法过程是必修1中学习过的什么算法？ 回答：枚举算法。 ”乱序扑克牌查找“———顺序查找过程演示： 问题： 若将上述问题规模扩大，在n张牌中寻找，则最理想情况是查找_____1__次？最差的情况需要查找____n____次？平均查找次数：___(n+1)/2_____。 平均查找次数：假设将数组中n个数据查找一次所使用的查找次数之和（1+2+3+4+......+n-1+n）再除以数据总个数n。平均查找次数为：(n+1)/2。 6、顺序查找算法程序实现： 算法框架：枚举算法框架（循环结构，循环体内使用分支结构） #key中存储要查找的数，待查找数据存储在d数组中。 for i in range（0,n,1）： #遍历数组索引 if d[i]==key： #如果查找成功，输出索引位置，并结束查找。 print(i) break else: #全部查找完毕没找到，输出“没找到！” print(“没找到！”) 顺序查找算法小结 三、【创设情境】：在新的扑克牌（ 新扑克牌按照A到K有序排列）中寻找”红桃5“，除了顺序查找有没有更高效的查找算法？（参考选择性必修1《数据与数据结构》第4章中的“猜数字游戏”的方法。） 回答：可以使用对分查找方法。 【探究学习对分查找】 1、对分查找算法思想： 首先将查找的数与有序数组内，处于中间位置的数据比较，如果中间位置上的数与查找的数不同，则根据数组的有序性，确定应该在数组的前半部分，还是后半部分继续查找。在新确定的范围内，继续按上述方法，直到获得最终结果。 2、新扑克牌查找“———对分查找自然语言描述： 问题描述：在不考虑扑克牌花色的情况下，仅在A到K,13张升序排列的扑克牌中寻找指定的牌。扑克牌2～ 10 为数字本身,A 为 1 ,J 为 11 ,Q 为 12 ,K 为 13，变量Key存储要查找的牌。 第一步：将13张扑克牌对应的数字（升序）存储于数组d中， 要查找的扑克牌对应数字储于变量key中。 第二步： 依次将d数组查找区间中间位置的数mid与key进行比较。 第三步： 若mid与key相等则查找成功结束查找,若key大于mid下一次查找区间为右半 ... ...