二分查找算法的程序实现教学设计高中信息技术新浙教版选修1数据与数据结构.docx
二分查找算法的程序实现教学设计课 程 标 准 和 教 学目 标二分查找算法的程序实现教材内容：5. 4查找 之 二分查找算法的程序实现适应的课程标准：1.7通过实现数据的排序和查找，体验迭代和递归的方法，理解算法与数据结构的关系。法。教学目标：掌握常用的二分查找的基本程序结构。能够编程实现二分查找。信息意识：学生能够结合生 活中的实例描述数据的内涵与外 延，有意识地选择恰当的数据结 构表达数据的逻辑关系。计算思维：能够从数据结构 的视角审视基于数组、链表的程 序，解释程序中数据的组织形式， 描述数据的逻辑结构及其操作， 评判其中数据结构运用的合理 性；能够针对限定条件的实际问 题进行数据抽象，运用数据结构 合理组织、存储数据，选择合适 的算法（排序、查找、迭代、递 归）编程实现、解决问题。数字化学习与创新：要使学 生能够较为熟练地运用数据结构 解决生活中的真实问题，并在此 过程中自主或协作探究；能够评 估常见的数字化资源与工具对学 习数据结构的价值，根据需要合 理选择。信息社会责任：能够分析数 据与社会各领域间的关系，自觉 遵守相应的伦理道德和法律法 规。学习环境：有教学控制软件的多媒体机房，python编程环境。建议课时：1课时教 学教学 环节教学过程设计 意图活情境 动导入 设计Key=12012345678910开始：6121518222528354658607L012345678910第一次比较:612151822252835465860t0Im"12345678910第二次比较：612151822252835465860012345678910第三次比较：612151822252835465860L- 1 01iJ2345678910第四次比较：6121518222528354658601”查找成功m 回顾一个对具体数据进行查找的基本过程。巩固旧 知，联 系新 知。学习 任务 *分查 找的 基本 过程 与规 则设计意 图：按 照由粗 到细、 逐步求 精的策 略，推 动学生 力口深对 二分查 找的深 认识。学习任务一：二分查找的基本过程与规则问题：二分查找是对查找键key在n个有序数据里面进行查找，查找过程是否有规则， 规则在哪里？引导学生思考并回答问题。引导学生总结：查找键key每次和区间内的中间位置元素进行比较，中点位置的计算： m=| （i + j） /2J,每次查找的基本过程。第一次，在查找范围（i, j）内的递增元素中找到中间位置，将查找键key值和中间位 置为5的元素d5进行比较，根据比较结果可以确定：在（m, j）内不可能存在值为key 的数据，必须在新的范围（i, m-1）中继续查找；第二次，在查找范围（i, m-1）内的递增元素中找到中间位置，将查找键key值和中间 位置为2的元素d2进行比较，根据比较结果可以确定：在（m, j）内不可能存在值为key 的数据，必须在新的范围（i, m-1）中继续查找；第三次，在查找范围（i, m-1）内的递增元素中找到中间位置，将查找键key值和中间 位置为0的元素d0进行比较，根据比较结果可以确定：在（i, m）内不可能存在值为key 的数据，必须在新的范围（m+1, j）中继续查找；第四次，在查找范围（m+1, j）内的递增元素中找到中间位置，将查找键key值和中间 位置为dl的元素12进行比较，找到key值。查找完成。以中间位置川、查找范围i、j变化为例，提炼出一般规则：学习 任务 *分查 找的 程序 实现教师引导学生用流程图来描述这个过程:学习任务二：二分查找的程序实现1.研究二分查找的第一次查找的程序实现这样，除了出现情况，在通过一次比较后，新的查找范围将不超过上一次查找范围的 一半。设问：再仔细观察某一次里面的查找过程，这种方法是否通用？教师引导学生总结：查找过程中，查找键key值与dm比较，结果必然是如下三种情况之一：key<dm查找键小于中点dm处的数据。由数组d中的数据的递增性，可以确 定：在（m, j）内不可能存在值为key的数据，必须在新的范围（i, m-1）中继 续查找。key=dm找到了需要的数据。keydm由于与相同的理由，必须在新的范围（m+1, j）中继续查找。仍以这些数据为例，回顾二分查找第一次的查找过程:Key=12开始:第一次比较：01234567891012151822252835465860012345678910121822252835465860二分查找算法对数组d的第一次查找过程设 计意 图：从 第一次 查找的 实现中 可以发 现规 律，进 而引导 学生概 括出全 部算法设问：经过第一次查找，key和dm的比较会出现几种情况？如何使用程序实现？过程。设计意 图：重 点在于 第一次 查找过 程，这 个过程 清楚 了，那 么对于 后面的 查找， 遵循同 样的规 则,以 此类 推，即 可实现 对数据 的查 找。止匕 处在于if dm = key: b=mif key < dm :#到左边去找j = m-1else:#到右边去找i = m + 1i、j代表数组元素的下标，i从0开始增大，j从length-1开始减小，i能否大于j? 为什么？2.设计算法实现二分查找设问：上一步中，我们编写了第一次查找的程序代码，如何修改一下，完成 整个查找过程？对于n个递增元素， 第一次查找将key 值和中间元素d m 进行比较，若找到 则退出程序，若比 dm小则到左区间 找，若比d m大则 到右区间找在新区间确定新的 中间元素dm,将 key值和dm进行 比较，重复刚才的 规律，直到找到key 值或找遍整个数组二分查找完 成i 二 0j = len(d)-l while i <= j:m = (i+j) /2 if dm = key:f=Trueb 二 m breakif key < dm :#到左边去找j = m-1else:#到右边去找i = m + 1d=6, 12, 15, 18, 22, 25, 28, 35, 46, 58, 60 f=False# i和j定义子数组的边界，一开始搜索的是整个数组 i = 0j = len(d)-l while i <= j: m = (i+j) /2 if dm = key: f=True b 二 m breakif key < dm :#到左边去找j = m-1else:#到右边去找i = m + 1 if f二二True:print (查找成功！第+str(b)+个) else:print (没有找到！)引导学 生意识 到什么 时候查 找结 束：找 到key 值或者 是当i 大于j 的时 候，其 实已经 把整个 数组全 都找遍 了。设 计意 图：由 第一次 查找的 代码， 概括出 查找的 规律， 是一种 抽象思 维的过 程，最 后将整 个过 程，进 f概 括出一 个循环 和判断 的程序 结构， 这是一 个难 点。可 以多花 些时4.二分查找延伸二分查找过程可用一棵二叉树来描述，树中的每个根结点对应当前查找区间的中点元 素，它的左子树和右子树分别对应该区间的左子表和右子表，如下图所示。通常把此树称为 二分查找的判定树。© © ® ®二分查找的判定树实例在有序表上二分查找一个关键字等于key的元素时，对应着判定树中从根结点到待查结 点的一条路径，同关键字进行比较的次数就等于该路径上的结点数，或者说等于待查结点的 层数。如上例中，查找key为12的元素时，从根结点到待查结点的一条路径为25 156 -12,比较次数为4次。通过观察可知，在n个兀素排序的顺序表里，某一次查找过程中，所做比较次数不超过判定树的高度加1,即log2 M + 1。由于二分查找在有序表上进行，所以其对应的判定树就是一棵二叉排序树。间，鼓 励学生 多思 考、多 动手、 多验 证。拓展 学习二分查找算法中，有序数组是递增排序和递减排序在程序实现时有何区别？ 若查找对象采用链表结构，能否适用二分查找？二分查找算法的递归实现？设计意 图：根 据学生 的不同 层次水 平设置 相应的 教学任 务。课堂 小结知识梳理：1 .二分查找算法的基本过程和结构；2 .二分查找算法的程序实现。二分查 找算法 的程序 实现是 难点，课 后作业 提供了 相应练 习。作业 布置基础作业（面向所有学生）：思考教材“问题与讨论”：若查找对象采用链表结构，能否适用二分查找？课后作 业是课 堂学习 的延伸， 是巩固 和升华 知识点 的有效 途径。教 学 设 计 思 路首先，引导学生回顾旧知，与前面所学的二分查找基本思想与方法建立联系，学生可以较熟悉地对若干 个数据进行二分查找。其次，引导学生能够从抽象的角度概括出二分查找的基本规则，并能以合适的数字化学习工具呈现出其 每次查找的基本过程。再次，在学生有了一定认知基础上，可以引入自然语言、流程图，帮助学生理解二分查找的基本程序结 构，从而实现对程序实现这个难点的突破。本节主要内容为查找算法的核心模块。针 对 核 心 素 养 培 养 的 设 计 考 虑本节侧重于计算思维的训练。程序语言是表达算法思想的工具，为了实现二分查找，在数据组织形式上 选择较为简单的整数，并从中概括出二分查找的基本过程和算法步骤。这是一个逐步求精的过程。为了照顾 普通学生的需要，可以从分析二分查找的第一次查找入手，然后再就其程序实现进行展开，这是一个由抽象 到具体的过程；然后再从第一次查找的实现，推广到查找结束，这是一个思维泛化的过程；再由此出发，抽 象出二分查找的整体程序结构，并通过简洁的代码实现，提炼出了二分查找的基本算法。这个基本过程，是 一种思维螺旋式上升的提升过程，较好地实现了教学意图。
