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

二分查找算法的程序实现教学设计二分查找算法的程序实现教材内容

5.4查找之二分查找算法的程序实现适应的课程标准

1.7通过实现数据的排序和查找，体验迭代和递归的方法，理解算法与数据结构的关系法教学目标信息意识学生能够结合生活中•掌握常用的二分查找的基本程序结构的实例描述数据的内涵与外延，有意识・能够编程实现二分查找地选择恰当的数据结构表达数据的逻辑关系计算思维能够从数据结构的视角审视基于数组、链表的程序，解释程序中数据的组织形式，描述数据的逻辑结构及其操作，评判其中数据结构运用课的合理性；能够针对限定条件的实际问程标题进行数据抽象，运用数据结构合理组准织、存储数据，选择合适的算法（排序、和查找、迭代、递归）编程实现、解决问教题学数字化学习与创新要使学生能目够较为熟练地运用数据结构解决生活中标的真实问题，并在此过程中自主或协作探究；能够评估常见的数字化资源与工具对学习数据结构的价值，根据需要合理选择信息社会责任能够分析数据与社会各领域间的关系，自觉遵守相应的伦理道德和法律法规学习环境有教学控制软件的多媒体机房，python编程环境建议课时1课时教教学环教学过程设计意图学节巩固旧活情境动导•学习任设计意回顾一个对具体数据进行查找的基本过程学习入设知，联务一二分查图按任务计系新Key=12找的基本过程照由粗■*知与规则到细、012345678910分查开始612151822252835465860问题二逐步求找的7L分查找是对查精的策基本找键key在n略，推过程012345678910第一次比较:612151822252835465860动学生个有序数据里与规Im力口深t面进行查找，则12345678910对二分查找过程是否查找的第二次比较有规则，规则612151822252835465860深认在哪里？引导识学生思考并回012345678910答问题第三次比较612151822252835465860i引导学L-1J生总结查找0键key每次和2345678910区间内的中间1第四次比较612151822252835465860位置元素进行1比较，中点位置的计算”查找成功m=|（i+j）m______________________________________________________/2J,每次查找的基本过程第一次，在查找范围（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[l]的元素12进行比较，找到key值查找完成以中间位置川、查找范围i、j变化为例，提炼出一般规则设问再仔细观察某一次里面的查找过程，这种方法是否通用？教师引导学生总结查找过程中，查找键key值与d[m]比较，结果必然是如下三种情况之一

①keyd[m]查找键小于中点d[m]处的数据由数组d中的数据的递增性，可以确定在（m,j）内不可能存在值为key的数据，必须在新的范围（i,m-1）中继续查找

②key=d[m]找到了需要的数据

③key〉d[m]由于与

①相同的理由，必须在新的范围（m+1,j）中继续查找这样，除了出现情况

②，在通过一次比较后，新的查找范围将不超过上一次查找范围的一半教师引导学生用流程图来描述这个过程:・学习任务二二分查找的程序实现学习设

1.研究二分查找的第一次查找的程序实现任务计意■■仍以这些数据为例，回顾二分查找第一次的查找过程:图从*第一次Key=12分查查找的找的012345678910实现中开始:12151822252835465860程序可以发实现现规012345678910律，进第一次比较121822252835465860而引导学生概括出全二分查找算法对数组d的第一次查找过程部算法过程设问经过第一次查找，key和d[m]的比较会出现几种情况？如何使用程序实现？if d[m]=key:b=mif keyd[m]:#到左边去找j=m-1else:#到右边去找i=m+1i、j代表数组元素的下标，i从0开始增大，j从length-1开始减小，i能否大于j为什么？

2.设计算法实现二分查找设问上一步中，我们编写了第一次查找的程序代码，如何修改一下，完成整个查找过程？在新区间确定新的中间二分查找完成对于n个递增元素，第一元素d[m],将key值和次查找将key值和中间元d[m]进行比较，重复刚素d[m]进行比较，若设计意才的规律，直到找到key找到则退出程序，若比图重点值或找遍整个数组d[m]小则到左区间找，在于第若比d[m]大则到右区间一次查找找过程，这个过程清楚了，那么对于后i二0面的查j=lend-l whilei=j:找，遵循m=i+j//2if d[m]==key:同样的f=True规则,以b二m break此类推，if keyd[m]:#到左边去找即可实j=m-1现对数else:#到右边去找据的查i=m+1找止匕处在于引导学生意识到什么时候查找结束找到keyd=[6,12,15,18,22,25,28,35,46,58,60]f=False值或者#i和j定义子数组的边界，一开始搜索的是整个数组i=0是当i大j=lend-l whilei=j:m=i+j//2if d[m]==key:f=True b二m break于j的时if keyd[m]:#到左边去找候，其实j=m-1已经把else:#到右边去找整个数i=m+1if f二二True:组全都print〃查找成功！第〃+strb+〃个〃else:找遍了print〃没有找到！〃设计意图由第一次查找的代码，概括出查找的规律，是

4.二分查找延伸一种抽二分查找过程可用一棵二叉树来描述，树中的每个根结点对应当前查找区间的中点元素，它的左子树象思维和右子树分别对应该区间的左子表和右子表，如下图所示通常把此树称为二分查找的判定树的过程，最后将整个过程，进f概括出一个循环和判断的程序结构，这是一个难点可以多©©®®花些时二分查找的判定树实例在有序表上二分查找一个关键字等于key的元素时，对应着判定树中从根结点到待查结点的一条路径，同关键字进行比较的次数就等于该路径上的结点数，或者说等于待查结点的层数如上例中，查找key为12的元素时，从根结点到待查结点的一条路径为25—15—6-12,比较次数为4次通过观察可知，在n个兀素排序的顺序表里，某一次查找过程中，间，鼓励所做比较次数不超过判定树的高度加1,即［log2M+1学生多由于二分查找在有序表上进行，所以其对应的判定树就是一棵二叉排序树思考、多动手、多验证二分查找算法中，有序数组是递增排序和递减排序在程序实现时有何区别？若查找对象采用链表结拓展学构，能否适用二分查找？设计意习二分查找算法的递归实现？图根据学生的不同层次水平设置相应的教学任务知识梳理课堂小

1.二分查找算法的基本过程和结构；结

2.二分查找算法的程序实现二分查找算法的程序实现是难点，课后作业提供了相应练习基础作业（面向所有学生）作业布思考教材“问题与讨论”若查找对象采用链表结构，能否适用二分查找？课后作业置是课堂学习的延伸，是巩固和升华知识点的有效途径首先，引导学生回顾旧知，与前面所学的二分查找基本思想与方法建立联系，学生可以较熟悉地对若干个数据进行二分查找其次，引导学生能够从抽象的角度概括出二分查找的基本规则，并能以合适的数字化学习工具呈现出其每次查找的基本教学过程设计再次，在学生有了一定认知基础上，可以引入自然语言、流程图，帮助学生理解二分查找的基本程序结构，从而实现对思路程序实现这个难点的突破本节主要内容为查找算法的核心模块针本节侧重于计算思维的训练程序语言是表达算法思想的工具，为了实现二分查找，在数据组织形式上选择较为简单的对整数，并从中概括出二分查找的基本过程和算法步骤这是一个逐步求精的过程为了照顾普通学生的需要，可以从分析二核分查找的第一次查找入手，然后再就其程序实现进行展开，这是一个由抽象到具体的过程；然后再从第一次查找的实现，推心广到查找结束，这是一个思维泛化的过程；再由此出发，抽象出二分查找的整体程序结构，并通过简洁的代码实现，提炼出素了二分查找的基本算法这个基本过程，是一种思维螺旋式上升的提升过程，较好地实现了教学意图养培养的设计考虑。