数据查找的应用教学设计
课程标准 和 教学目标 数据查找的应用
教材内容：5.4数据查找的应用
适应的课程标准： 1.7 通过实现数据的排序和查找，体验迭代和递归的方法，理解算法与数据结构的关系。
教学目标： ●能针对具体的问题情境，选择合适的数据查找算法。 ●能够完整地进行抽象与建模、设计算法与数据结构、程序实现，解决查找算法的应用问题。 指向的核心素养： ●信息意识：学生能够结合生活中的实例描述数据的内涵与外延，有意识地选择恰当的数据结构表达数据的逻辑关系。 ●计算思维：能够将有限制条件的、复杂生活情境中的关系进行抽象，能够从数据结构的视角审视基于数组、链表的程序，解释程序中数据的组织形式，描述数据的逻辑结构及其操作，评判其中数据结构运用的合理性；能够针对限定条件的实际问题进行数据抽象，运用数据结构合理组织、存储数据，选择合适的算法（排序、查找、迭代、递归）编程实现、解决问题。 ●数字化学习与创新：要使学生较为熟练地运用数据结构解决生活中的真实问题，并在此过程中自主或协作探究；能够评估常见的数字化资源与工具对学习数据结构的价值，根据需要合理选择。 ●信息社会责任：能够分析数据与社会各领域间的关系，自觉遵守相应的伦理道德和法律法规。
学习环境：有教学控制软件的多媒体机房，python编程环境。
建议课时：1课时
教学环节 教学过程 设计意图
情境导入 导入1：航空公司VIP会员积分查询部分数据（Excel数据） VIP号姓名飞行里程（KM）积分600214韩江辉16801 519601278蒋志来5321 78600815李亚东28745 436607854王庆生1861 39605719李燕7493 138603532王晓燕6875 102600101郑煜明14253 236600087蔡佳宁112703 958
请学生操作Excel表，要求实现根据VIP号码快速查询会员积分。查找如何实现？ 设计意图：通过导入生活中的数据分析案例，体会查找过程中要显示某个会员的积分信息，先得从多条记录中查找到该会员的记录。
新课讲解 ●学习任务一：抽象与建模 问题：从表中的数据可以看出，每个会员的信息是一条记录，包括VIP号、姓名、飞行里程、积分等数据项。根据刚才的实践体验，对记录快速查询会员积分，查找应当如何进行？ 教师总结：查找过程中要显示某个会员的积分信息，先得从多条记录中查找到该会员的记录，如下所示： XXXXXXXXXXXXXX XXX
若用a[i]表示该条记录，则该会员的积分可采用以下形式表示： a[i][3]（表示该条记录的第4个数据项的值） ●学习任务二：设计算法与数据结构 对于每个会员，需要记录其一条完整的记录信息，查找之前要将所有会员的信息存储起来，可以选取数组结构来实现。 有两种方案： 一是采用4个一维数组按列存储，即每个数组分别存储每位会员的VIP号、姓名、飞行里程（km）和积分，如定义b数组存储表中8位会员的积分，其对应的值为[519,78,436,39,138,102,236,958]； 二是采用1个一维数组按行存储，每个数组元素对应某位会员的一条记录信息，如[600214,韩江辉,16801,519]对应VIP号600214的相关信息。 采用不同的存储方式，排序时数据的交换方式也有不同。根据5.3.3排序算法的应用，采用1个一维数组按行存储处理起来更方便快捷。 要显示某个会员的积分，先要从多条会员信息的数据中找到该会员。查找可采用顺序查找算法或二分查找算法，若从算法的时间复杂度方面考虑，对数据进行一次查找，哪一种查找算法的效率高；对数据重复查找，哪一种查找算法的效率高？学生可以展开小组讨论。 老师总结： 对数据进行一次查找，采用顺序查找算法。对数据重复查找，二分查找算法的效率高于顺序查找算法，但二分查找提前：被查找的数据序列必须是有序，即在查找前要按VIP号为关键字进行排序。 设问：综合考虑应该采用哪一种查找算法？ ●学习任务三：程序实现 老师可以提供数据样例，并以csv格式文件分发给学生。读取数据文件时，选择一个一维数组，然后采用二分查找算法进行查找。根据学习情况，读写csv文件的程序代码可以由老师提供给学生。 示例程序： import csv #数据读入 csvFile = open("vip.csv", "r") reader = csv.reader(csvFile) a = [] for item in reader: a.append(item) csvFile.close() #排序 def bubble_sort(d): for i in range(1,len(d)): for j in range(1,len(d)-i): if int(d[j][0])>int(d[j+1][0]): temp=d[j] d[j]=d[j+1] d[j+1]=temp #二分查找 def bsearch(s,array): i = 1 #查找范围不包含第一行数据 j = len(array)-1 while i <= j: m = (i+j) //2 if int(array[m][0]) ==s: return m if s < int(array[m][0]): 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(a[m][1],"先生/女士，',您的积分为：",a[m][3]) else: print('找不到VIP号对应的用户信息！')
设计意图：引导学生思考复杂数据查找的规律。 设计意图：引导学生比较不同查找算法的效率，考虑每种查找算法的局限性，二分查找算法的前提被查找的数据序列必须是有序。 设计意图：可以在配合讲解程序的情况下，鼓励学生自己动手编写程序。老师可以巡视过程中发现问题，帮助解决问题。
课堂小结 知识梳理 1. 抽象数据类型的数据查找； 2. 不同应用场景下不同查找算法的效率； 3. 抽象与建模、设计算法与数据结构、程序实现的完整经过。 学习评价 对自己和同伴的表现进行客观的评价，并思考后续完善的方向。（5=优秀，4=超出一般水平，3=满意，2=有待改进，1=不太理想） 评分项自我评价同学互评能完成新课导入中的问题并理解记录中积分查找的一般步骤5 4 3 2 15 4 3 2 1掌握并比较不同应用场景下不同查找算法的效率5 4 3 2 15 4 3 2 1能够掌握抽象与建模、设计算法与数据结构、程序实现的完整经过5 4 3 2 15 4 3 2 1
设计意图：针对不同学习程度设计对应的任务，以满足不同学生的需求。
作业布置 基础作业（面向所有学生）： 思考教材“问题与讨论”：在“航空公司VIP会员积分查询”例子中，将其中的二分查找改成顺序查找，并上机实践。 课后作业是课堂学习的延伸，是巩固和升华知识点的有效途径。
教学设计思路 本条目建议重点关注计算思维的培养与提高。建议从学生熟悉的生活情境出发，由学生已经获得的编程经验自然延伸、生发，针对具体问题展开。可从抽象与建模、设计算法与数据结构、程序实现三个方面进行。即通过合适途径让学生明晰查找算法应用时应当注意的问题，特别是面对较复杂结构的数据时，如果数据以记录的形式呈现，各条记录的查找如何进行，涉及查找的具体操作时，有哪些注意事项。据此再讨论算法的设计，对数据的组织形式展开讨论，并详细剖析不同的查找方法有什么差异。厘清问题是程序实现的关键所在，选择合适的数据结构和合适的查找算法之后，再针对具体实现讲解要点，鼓励学生自主完成。同时可以就不同的查找算法对程序实现的效率进行分析，帮助学生认识到查找算法对解决问题的重要影响。
针对 核心素养培养的 设计考虑 信息意识、信息社会责任：本节课在导入时选择了一个案例，导入“航空公司VIP会员积分查询部分数据（Excel数据）”，由于Excel表格进行查找操作时，直观形象，教师可以引导学生思考查找的一般步骤、抽象数据类型、顺序查找算法和二分查找算法的优劣，从而形成对记录查找相关问题初步的意识。 计算思维：本节中围绕较为复杂形式的数据如何进行查找展开，这是一个由抽象与建模、设计算法与数据结构、程序实现组成的完整经过。 数字化学习与创新：本节的数据可以从真实环境中产生，或者由老师提前安排好并提供数据文件，或者由学生课前自主搜集相关数据。鼓励学生利用多途径方式收集数据，并采用不同的查找算法进行数据查找算法的探索。二分查找算法的思想教学设计
课程标准 和 教学目标 二分查找算法的思想
教材内容：5.4.2 常见的查找算法中的二分查找
适应的课程标准： 1.6通过列举实例，认识到抽象数据类型对数据处理的重要性，理解抽象数据类型的概念，了解二叉树的概念及其基本操作方法。
教学目标： ●通过对生活实例的分析和描述，理解二分查找的概念和基本方法。 ●能根据数据是否有序，选择不同的查找方法。 ●能根据二分查找的思想和特点，通过分步解析获取二分查找的解题结构。 指向的核心素养： ●信息意识：能够根据解决问题的需要，自觉、主动地寻求恰当的方式获取与处理信息。 ●计算思维：针对给定的问题情境进行问题分析，抽象问题的基本特征，设计算法与数据结构，编程解决问题。 ●数字化实践：能够较为熟练地运用数据结构解决生活中真实问题，并在解决问题的过程中进行选择合适的数字化资源与工具进行自主学习与小组协作探究。
学习环境：有教学控制软件的多媒体机房。
建议课时：1课时
教学活动设计 教学环节 教学过程 设计意图
情境导入 引入1：师生一起玩猜数字游戏。教师在纸上写下一个数字，让学生来猜这个数字，学生根据教师提示“大了”或是“小了”猜出纸上的数字。师生共同讨论游戏中蕴含的算法。 引入2：观看视频“如何迅速的找到东西”，了解二分查找算法的基本思想。 通过让学生完成猜数字的游戏以及观看视频，自然地进入课堂，让学生初步体验二分查找算法，对该算法有初步感性认识。
知识讲解 1. 通过分析上述视频，讨论二分法查找算法是怎样查找的？它的实现有没有什么条件？比较顺序查找和二分查找算法的区别。 2. 教师以教材中规模为11的数组d为例，讲解二分查找的过程。在数组d的11个元素中，已按升序存储了11个数据，要寻找的数据为12（已存储在变量key中）。 有了对两种查找算法的对比分析后，学生对二分查找算法有了进一步的理解，从而实现知识的内化。 通过教师的讲解，帮助学生进一步理解二分查找算法的基本过程。
自主学习 1.让学生自主学习教材中“二分查找的基本方法”，讨论如何确定查找区间中点m的位置？ 2.学生根据上述实例数据，小组合作讨论查找范围（i,j）的变化情况。 3.教师根据学生的回答，总结归纳： ①首先确定查找区间的中点位置：
m= （表示小于等于的最大整数） ②然后将查找键key值与d[m]比较，结果必然是如下三种情况之一： A. keyd[m] 根据数组d中的数据递增性，可以确定新的查找范围为（m+1，j）。 4. 学生将上述实例数据改为递减，写出用二分查找算法在递减数组d查找时，查找键key值与d[m]比较的三种情况。 帮助学生通过分析实例数据来理解查找范围（i,j）的变化情况，而不是机械地记住抽象枯燥的结果。 通过对升序、降序数组查找范围（i,j）变化情况的分析总结，帮助学生加深对二分查找算法的理解。
课堂小结 知识梳理： 1.总结二分查找算法的基本思想，比较顺序查找和二分查找的区别； 2.总结二分查找算法的特点及适用范围； 3.总结二分查找的基本方法，确定查找区间中点m的位置； 4.总结查找键key值与d[m]比较的三种情况。 通过分析实例，培养学生对二分查找算法的感性认识，为深刻理解算法提供事实基础；有了事实基础和体验过程，还需要对知识进行归纳和总结，纳入原有知识结构，实现知识的升华。
教学设计思路 本课通过让师生一起玩猜数字游戏引入，师生共同讨论游戏中蕴含的算法。通过观看视频“如何迅速的找到东西”，了解二分查找算法的基本思想。让学生初步体验二分查找算法，对该算法有初步感性认识。 通过分析视频，讨论二分法查找算法是怎样查找的？它的实现有没有什么条件？比较顺序查找和二分查找算法的区别。有了对两种查找算法的对比分析后，学生对二分查找算法有了进一步的理解，从而实现知识的内化。 教师以教材中规模为11的数组d为例，讲解二分查找的过程。在数组d的11个元素中，已按升序存储了11个数据，要寻找的数据为12（已存储在变量key中）。通过教师的讲解，帮助学生进一步理解二分查找算法的基本过程。 学生通过自主学习教材中“二分查找的基本方法”，讨论确定查找区间中点m的位置。分组讨论查找范围（i,j）的变化情况。教师根据学生的回答，进行总结归纳。 课堂小结对二分查找算法的知识进行归纳和总结，纳入原有知识结构，实现知识的升华。 本节课的内容总体难度不大，教师提供适量的生活实例启发学生思考，学生比较容易理解掌握二分查找的基本思想。在给予学生足够的时间自主学习后，通过分组讨论，掌握二分查找的基本方法。
针对 核心素养培养的 设计考虑 核心素养的培养不可能泛泛而谈，而应落实在每一次引导、每一个活动之中。本条例各个核心素养的具体落点分析如下： 信息意识：落点在“能够根据解决问题的需要，自觉、主动地寻求恰当的方式获取与处理信息”。本条目通过不同的应用场景，让学生在熟悉的例子中进入二分查找算法的学习，唤起学生的兴趣，引导学生在熟悉的真实情境中理解二分查找算法的概念，分析在不同的情境中可以恰当地运用不同的查找方法达到最快速度的查找。 计算思维：落点在“针对给定的任务进行需求分析，明确需要解决的关键问题；能提取问题的基本特征，进行抽象处理，并用形式化的方法表述问题”。本条例通过小组交流讨论，使学生从抽象到具体地理解二分算法的基本方法和适应范围，体验从问题到算法的思维历程，提炼二分查找算法的步骤与方法，在讨论中总结查找键key值与d[m]比较的三种情况，提升学生的计算思维。 数字化学习与创新：落点在“能够较为熟练地运用数据结构解决生活中真实问题，并在解决问题的过程中进行选择合适的数字化资源与工具进行自主学习与小组协作探究”。在拓展学习任务时，鼓励学生根据实际解决问题的需要，使用数字化工具开展自主学习和协同工作，并能在解决问题的过程中优化算法思想，提升创新能力。查找的概念、顺序查找的思想及程序实现教学设计
课程标准 和 教学目标 查找的概念、顺序查找的思想及程序实现
教材内容：5.4.1 查找 5.4.2 常见的查找算法中的顺序查找
适应的课程标准： 1.7 通过实现数据的排序和查找，体验迭代和递归的方法，理解算法与数据结构的关系。
教学目标： ●通过对生活实例的分析和描述，理解查找的概念。 ●通过不同生活实例的对比分析，学会选择运用恰当的查找方法进行问题解决。 ●理解顺序查找的思想。 ●能够针对具体给定的问题情境，合理组织数据，使用顺序查找的算法编程实现。 指向的核心素养： ●信息意识：能够根据解决问题的需要，自觉、主动地寻求恰当的方式获取与处理信息。 ●计算思维：针对给定的问题情境进行问题分析，抽象问题的基本特征，设计算法与数据结构，编程解决问题。 ●数字化实践：能够较为熟练地运用数据结构解决生活中真实问题，并在解决问题的过程中进行选择合适的数字化资源与工具进行自主学习与小组协作探究。
学习环境：有教学控制软件的多媒体机房。
建议课时：1课时
教学活动设计 教学环节 教学过程 设计意图
情境导入 导入1：拿出一副新牌，如何快速找到其中一张牌。 导入2：将牌打乱后，怎么再寻找这张牌。 思考：生活中还有哪些查找的具体例子，你是通过什么样的方法快速进行查找的。（例如：查字典、查电话号码等） 通过让学生对比有规律的扑克牌和无序的扑克牌找一张牌的不同方法，体验不同的查找过程，激发学生的学习兴趣，自然地引入新课，对查找算法有初步感性认识。 通过学生自己举例生活中的查找实例，进一步提升学生的信息意识，在与同学分享自己最优的查找方法的过程中，锻炼了学生的语言表达能力和计算思维能力。
自主学习 1. 通过分析上述生活中的实例，学生结合自主学习5.4.1部分内容，总结得出算法概念。 2. 自主学习5.4.2顺序查找的思想部分内容，请学生用自然语言描述算法步骤。 教师根据学生的回答，总结算法描述： ①将待查找的数据储存在数组中； ②输入查找关键值key； ③从数组中的第一个元素开始与关键值key进行比较，若相等，则输出相应信息；否则，继续比较下一个元素。 ④直到找完数组的最后一个元素仍不想等，输出查找失败。 有了对实际案例的对比分析后，学生对查找算法有了初步感性认识，趁热打铁，让学生根据教材内容归纳总结查找算法的概念，从而实现知识的内化。 顺序查找的内容较为简单直白，学生可以通过自学该部分内容理清算法思路，教师只需从旁引领提示即可。
学生上机实践 题目： A数组中存放了一些动物名称“dog” “cat” “monkey” “tiger” “panda” “rabbit” “horse”，现在想查找动物“bear”是否在其中，如找到输出“查找成功！是第几个动物”，否则输出“查找失败”，无论查找成功与否都输出比较的次数。 设计意图：学生在知道了顺序查找的基本思想后，读懂书本中的代码是比较简单的，因此教师布置了一个课本上稍作改变的例子让学生上机实践，既降低了难度，又让学生对代码进一步巩固加深印象。在输出查找成功与否的基础上统计查找的次数，为后面查找次数效率的分析打下基础。
拓展提升（选做） 某个班级的部分学生语文成绩如下表所示，要求实现根据考号查询该生的语文成绩，如查询不到则显示“该班无此学生”。 思考： （1）用哪一种数据结构对表格数据进行存储？ （2）对哪个字段进行顺序查找？ 说明：应用数组存储表中的数据，可以用3个一维数组也可以用1个一维数组；并对每一个字段的作用功能进行分析，顺序查找的为考号字段，结果显示的是语文字段值。 对于学有余力的学生，可以参考书本中的代码，将顺序查找部分代码进行函数的改编，以便于反复进行调用 设计两个思考问题帮助学生通过分析实例理清思路，抽象建立数学模型。拓展任务的设置让学有余力的同学可以结合生活实例去思考解决实际问题，培养优秀学生的自主学习能力和探索精神，提高学生的计算思维能力，真正实现学以致用。同时在该时间段内让写程序比较困难的学生有足够的时间进行代码的思考编写调试。
课堂小结 思考： （1）若一个班级一共有45人，查找成功最好情况是比较几次？最差呢？若查找不成功，需要比较几次？ （2）若有N个数据，那顺序查找的平均比较次数为几次？ 教师总结归纳：若一个数据序列有n个数，查找不成功的比较次数为n，查找成功：最好的情况为1次，最差的情况为n次，所以查找成功时的平均比较次数为(n+1)/2，且顺序查找的时间复杂度为O(n) 从具体例子引发学生思考，再抽象到n个数据的情况，总结归纳出一般情况，符合学生的思维习惯。
教学设计思路 本课通过让学生分析未打乱的扑克牌和打乱的扑克牌寻找同一张扑克牌的情境引入，启发学生运用不同的查找方法来快速解决问题，引导学生抽象两个不同问题的基本特征，将具体的例子抽象归纳出一般特征即查找对象是有序还是无序这一特征来选择不同的查找方法。在两个生活中具体问题的查找实践过程中领会查找算法的概念。 有了对实际案例的对比分析后，学生对查找算法有了初步感性认识，趁热打铁，让学生根据自己的生活经验自己举例相关的例子和查找方法，从而进一步实现知识的内化。 顺序查找思想部分的内容较为简单直白，学生可以通过自学主学习该部分内容理清算法思路，教师只需从旁引领提示即可。教师根据学生的回答归纳总结出顺序查找思想的自然语言描述。 学生在知道了顺序查找的基本思想后，读懂书本中的代码是比较简单的，因此从自然语言直接过渡到程序语言没有太大难度，此时跳过流程图的步骤，直接让学生读课本中的样例。上机实践部分如果直接做课本中的例子，学生会觉得枯燥乏味，不动脑筋的照样打一遍代码，不利于学生对代码的真正理解内化，因此教师布置了一个课本上稍作改变的例子让学生上机实践，学生在参考书本代码的基础上，进行模仿改写，既降低了难度，又让学生对代码进一步巩固加深印象。最后在输出查找成功与否的基础上统计查找的次数，为后面查找次数效率的分析打下基础。 在完成基本任务后，对于学有余力的学生安排了拓展任务，培养优秀学生的自主学习能力和探索精神，提高学生的计算思维能力，真正实现学以致用。此任务为一个接近学生生活的现实问题，利用顺序查找的算法来解决该问题。在代码编写之前设计两个思考问题帮助学生通过分析实例理清思路，抽象建立数学模型。同时在该时间段内让写程序比较困难的学生有足够的时间进行前一个代码的思考编写调试。 课堂小结主要归纳总结顺序查找的时间复杂度，从具体例子的最坏最好情况的查找比较次数，引发学生思考一般情况，抽象出n个数据的各种情况，这样符合学生的思维习惯。 本节课的内容总体难度不大，教师提供适量的生活实例启发学生思考，学生比较容易理解掌握顺序查找的基本思想。在给予学生足够的时间自主学习后，通过上机实践操作，掌握顺序查找的程序实现。
针对 核心素养培养的 设计考虑 核心素养的培养不可能泛泛而谈，而应落实在每一次引导、每一个活动之中。本条例各个核心素养的具体落点分析如下： 信息意识：落点在“能够根据解决问题的需要，自觉、主动地寻求恰当的方式获取与处理信息；”。本条目通过不同的生活应用场景，让学生在熟悉的例子中进入查找算法的学习，唤起学生的兴趣，引导学生在熟悉的真实情境中理解查找算法的概念，分析在不同的情境中可以恰当地运用不同的查找方法达到最快速度的查找。 计算思维：落点在“针对给定的问题情境进行问题分析，抽象问题的基本特征，设计算法与数据结构，编程解决问题”。本条目帮助学生在身边熟悉的情境中理解查找的概念和常见的查找方法，能根据特定的问题情境进行问题分析，例如引入部分未打乱的扑克牌和打乱的扑克牌寻找同一张扑克牌的情境，需要运用不同的查找方法来快速解决问题，引导学生抽象两个不同问题的基本特征，将具体的例子抽象归纳出一般特征即查找对象是有序还是无序。在具体的上机实践过程中，以一个查找动物位置一个虚拟的例子铺垫，然后进一步提升到现实具体问题的解决，在现实问题解决过程中设计合适的数据结构来存储数据，选择合适的查找算法，并在编程实现的过程中进一步提升学生的计算思维。 数字化学习与创新：落点在“能够较为熟练地运用数据结构解决生活中真实问题，并在解决问题的过程中进行选择合适的数字化资源与工具进行自主学习与小组协作探究”。在拓展学习任务时，鼓励学生根据实际解决问题的需要，使用数字化工具开展自主学习和协同工作，并能在解决问题的过程中优化算法思想，提升创新能力。二分查找算法的程序实现教学设计
课程标准 和 教学目标 二分查找算法的程序实现
教材内容：5.4查找 之 二分查找算法的程序实现
适应的课程标准： 1.7 通过实现数据的排序和查找，体验迭代和递归的方法，理解算法与数据结构的关系。 法。
教学目标： ●掌握常用的二分查找的基本程序结构。 ●能够编程实现二分查找。 信息意识：学生能够结合生活中的实例描述数据的内涵与外延，有意识地选择恰当的数据结构表达数据的逻辑关系。 计算思维：能够从数据结构的视角审视基于数组、链表的程序，解释程序中数据的组织形式，描述数据的逻辑结构及其操作，评判其中数据结构运用的合理性；能够针对限定条件的实际问题进行数据抽象，运用数据结构合理组织、存储数据，选择合适的算法（排序、查找、迭代、递归）编程实现、解决问题。 数字化学习与创新：要使学生能够较为熟练地运用数据结构解决生活中的真实问题，并在此过程中自主或协作探究；能够评估常见的数字化资源与工具对学习数据结构的价值，根据需要合理选择。 信息社会责任：能够分析数据与社会各领域间的关系，自觉遵守相应的伦理道德和法律法规。
学习环境：有教学控制软件的多媒体机房，python编程环境。
建议课时：1课时
教学活动设计 教学环节 教学过程 设计意图
情境导入 回顾一个对具体数据进行查找的基本过程。 巩固旧知，联系新知。
学习任务一：二分查找的基本过程与规则 ●学习任务一：二分查找的基本过程与规则 问题：二分查找是对查找键key在n个有序数据里面进行查找，查找过程是否有规则，规则在哪里？引导学生思考并回答问题。 引导学生总结：查找键key每次和区间内的中间位置元素进行比较，中点位置的计算： m=，每次查找的基本过程。 第一次，在查找范围（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]比较，结果必然是如下三种情况之一： keyd[m] 由于与①相同的理由，必须在新的范围（m+1，j）中继续查找。 这样，除了出现情况②，在通过一次比较后，新的查找范围将不超过上一次查找范围的一半。 教师引导学生用流程图来描述这个过程： 设计意图：按照由粗到细、逐步求精的策略，推动学生加深对二分查找的深认识。
学习任务二：二分查找的程序实现 ●学习任务二：二分查找的程序实现 1. 研究二分查找的第一次查找的程序实现 仍以这些数据为例，回顾二分查找第一次的查找过程： 二分查找算法对数组d的第一次查找过程 设问：经过第一次查找，key和d[m]的比较会出现几种情况？如何使用程序实现？ (
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 = 0
j = len(d)-1
while i <= j:
m = (i+j) //2
if d[m] == key:
f=True
b=m
break
if key < d[m]: # 到左边去找
j = m-1
else:
# 到右边去找
i = m + 1
) 3. 学生动手编写二分查找的程序实现 (
d=[6,12,15,18,22,25,28,35,46,58,60]
f=False
# i和j定义子数组的边界，一开始搜索的是整个数组
i = 0
j = len(d)-1
while i <= j:
m = (i+j) //2
if d[m] == key:
f=True
b=m
break
if key < d[m]: # 到左边去找
j = m-1
else:
# 到右边去找
i = m + 1
if f==True:
print("查找成功！第"+str(b)+"个")
else:
print("没有找到！")
) 4.二分查找延伸 二分查找过程可用一棵二叉树来描述，树中的每个根结点对应当前查找区间的中点元素，它的左子树和右子树分别对应该区间的左子表和右子表，如下图所示。通常把此树称为二分查找的判定树。 二分查找的判定树实例 在有序表上二分查找一个关键字等于key的元素时，对应着判定树中从根结点到待查结点的一条路径，同关键字进行比较的次数就等于该路径上的结点数，或者说等于待查结点的层数。如上例中，查找key为12的元素时，从根结点到待查结点的一条路径为25→15→6→12，比较次数为4次。通过观察可知，在n个元素排序的顺序表里，某一次查找过程中，所做比较次数不超过判定树的高度加1，即。 由于二分查找在有序表上进行，所以其对应的判定树就是一棵二叉排序树。 设计意图：从第一次查找的实现中可以发现规律，进而引导学生概括出全部算法过程。 设计意图：重点在于第一次查找过程，这个过程清楚了，那么对于后面的查找，遵循同样的规则，以此类推，即可实现对数据的查找。此处在于引导学生意识到什么时候查找结束：找到key值或者是当i大于j的时候，其实已经把整个数组全都找遍了。 设计意图：由第一次查找的代码，概括出查找的规律，是一种抽象思维的过程，最后将整个过程，进一步概括出一个循环和判断的程序结构，这是一个难点。可以多花些时间，鼓励学生多思考、多动手、多验证。
拓展学习 二分查找算法中，有序数组是递增排序和递减排序在程序实现时有何区别？ 若查找对象采用链表结构，能否适用二分查找？ 二分查找算法的递归实现？ 设计意图：根据学生的不同层次水平设置相应的教学任务。
课堂小结 知识梳理： 1. 二分查找算法的基本过程和结构； 2. 二分查找算法的程序实现。 二分查找算法的程序实现是难点，课后作业提供了相应练习。
作业布置 基础作业（面向所有学生）： 思考教材“问题与讨论”：若查找对象采用链表结构，能否适用二分查找？ 课后作业是课堂学习的延伸，是巩固和升华知识点的有效途径。
教学设计思路 首先，引导学生回顾旧知，与前面所学的二分查找基本思想与方法建立联系，学生可以较熟悉地对若干个数据进行二分查找。 其次，引导学生能够从抽象的角度概括出二分查找的基本规则，并能以合适的数字化学习工具呈现出其每次查找的基本过程。 再次，在学生有了一定认知基础上，可以引入自然语言、流程图，帮助学生理解二分查找的基本程序结构，从而实现对程序实现这个难点的突破。 本节主要内容为查找算法的核心模块。
针对 核心素养培养的 设计考虑 本节侧重于计算思维的训练。程序语言是表达算法思想的工具，为了实现二分查找，在数据组织形式上选择较为简单的整数，并从中概括出二分查找的基本过程和算法步骤。这是一个逐步求精的过程。为了照顾普通学生的需要，可以从分析二分查找的第一次查找入手，然后再就其程序实现进行展开，这是一个由抽象到具体的过程；然后再从第一次查找的实现，推广到查找结束，这是一个思维泛化的过程；再由此出发，抽象出二分查找的整体程序结构，并通过简洁的代码实现，提炼出了二分查找的基本算法。这个基本过程，是一种思维螺旋式上升的提升过程，较好地实现了教学意图。
