5.4.3 二分查找算法的程序实现 教学设计-高中信息技术浙教版选修1 数据 与数据结构.docx

二分查找算法的程序实现教学设计 课程标准 和 教学目标 二分查找算法的程序实现 教材内容：5.4查找　之　二分查找算法的程序实现 适应的课程标准： 1.7 通过实现数据的排序和查找，体验迭代和递归的方法，理解算法与数据结构的关系。 法。 教学目标： ●掌握常用的二分查找的基本程序结构。 ●能够编程实现二分查找。 信息意识：学生能够结合生活中的实例描述数据的内涵与外延，有意识地选择恰当的数据结构表达数据的逻辑关系。 计算思维：能够从数据结构的视角审视基于数组、链表的程序，解释程序中数据的组织形式，描述数据的逻辑结构及其操作，评判其中数据结构运用的合理性；能够针对限定条件的实际问题进行数据抽象，运用数据结构合理组织、存储数据，选择合适的算法（排序、查找、迭代、递归）编程实现、解决问题。 数字化学习与创新：要使学生能够较为熟练地运用数据结构解决生活中的真实问题，并在此过程中自主或协作探究；能够评估常见的数字化资源与工具对学习数据结构的价值，根据需要合理选择。 信息社会责任：能够分析数据与社会各领域间的关系，自觉遵守相应的伦理道德和法律法规。 学习环境：有教学控制软件的多媒体机房，python编程环境。 建议课时：1课时 教学活动设计 教学环节 教学过程 设计意图 情境导入 回顾一个对具体数据进行查找的基本过程。 巩固旧知，联系新知。 学习任务一：二分查找的基本过程与规则 ●学习任务一：二分查找的基本过程与规则 问题：二分查找是对查找键key在n个有序数据里面进行查找，查找过程是否有规则，规则在哪里？引导学生思考并回答问题。 引导学生总结：查找键key每次和区间内的中间位置元素进行比较，中点位置的计算： m=（i+j）/2 第一次，在查找范围（i，j）内的递增元素中找到中间位置，将查找键key值和中间位置为5的元素d[5]进行比较，根据比较结果可以确定：在（m，j）内不可能存在值为key的数据，必须在新的范围（i，m-1）中继续查找； 第二次，在查找范围（i，m-1）内的递增元素中找到中间位置，将查找键key值和中间位置为2的元素d[2]进行比较，根据比较结果可以确定：在（m，j）内不可能存在值为key的数据，必须在新的范围（i，m-1）中继续查找； 第三次，在查找范围（i，m-1）内的递增元素中找到中间位置，将查找键key值和中间位置为0的元素d[0]进行比较，根据比较结果可以确定：在（i，m）内不可能存在值为key的数据，必须在新的范围（m+1，j）中继续查找； 第四次，在查找范围（m+1，j）内的递增元素中找到中间位置，将查找键key值和中间位置为d[1]的元素12进行比较，找到key值。 查找完成。 以中间位置m、查找范围i、j变化为例，提炼出一般规则： 设问：再仔细观察某一次里面的查找过程，这种方法是否通用？ 教师引导学生总结：查找过程中，查找键key值与d[m]比较，结果必然是如下三种情况之一： key<d[m] 查找键小于中点d[m]处的数据。由数组d中的数据的递增性，可以确定：在（m，j）内不可能存在值为key的数据，必须在新的范围（i，m-1）中继续查找。 key=d[m] 找到了需要的数据。 key>d[m] 由于与①相同的理由，必须在新的范围（m+1，j）中继续查找。 这样，除了出现情况②，在通过一次比较后，新的查找范围将不超过上一次查找范围的一半。 教师引导学生用流程图来描述这个过程： 设计意图：按照由粗到细、逐步求精的策略，推动学生加深对二分查找的深认识。 学习任务二：二分查找的程序实现 ●学习任务二：二分查找的程序实现 1. 研究二分查找的第一次查找的程序实现 仍以这些数据为例，回顾二分查找第一次的查找过程： 二分查找算法对数组d的第一次查找过程 设问：经过第一次查找，key和d[m]的比较会出现几种情况？如何使用程序实现？ if d[m] == key: if d[m] == key: b=m if key < d[m]: # 到左边去找 j = m-1 else: # 到右边去找 i = m + 1 i、j代表数组元素的下标，i从0开始增大，j从length-1开始减小，i能否大于j？为什么？ 2. 设计算法实现二分查找 设问：上一步中，我们编写了第一次查找的程序代码，如何修改一下，完成整个查找过程？ 对于 对于n个递增元素，第一次查找将key值和中间元素d[m]进行比较，若找到则退出程序，若比d[m]小则到左区间找，若比d[m]大则到右区间找 在新区间确定新的中间元素d[m]，将key值和d[m]进行比较，重复刚才的规律，直到找到key值或找遍整个数组 二分查找完成 i