二分法查找教学设计
江苏省东台中学 朱世华
一、教学课题
第三章第三节《二分法查找》——算法与程序设计（新课标教科书；教育科学出版社）
二、教材及学者分析
《二分法查找》这部分知识在新课程数学必修1中已经涉及到，在前面的知识中，学生基本掌握数组的简单应用，并且已经能够利用顺序查找方法对某个数据队列进行单个数据查找。本节课主要让学生掌握二分法查找的基本思想，并将这一算法体现到具体的实例中，从而提高解决问题的效率。
三、教学目标
1、认知目标
理解二分法查找算法的基本思想。
2、技能目标
掌握二分法查找算法的简单应用（编写猜数小游戏）。
3、情感目标
培养学生的自主学习、互相协作、分析问题的能力。
4、教学重点
二分法查找算法的理解。
四、教法与学法
1、教法：任务驱动法、范例教学法、情境教学法
2、学法：自主式学习、互助式学习
说明：开课请同学参与完成两游戏，这两游戏和学生的编程思想是紧密相连的，所以游戏的导入一方面是引起学生学习的热情，另一方面也是让学生领会编程设计方法：二分法。为下面教学活动的开展做好铺垫。根据学生接受知识的能力不同，将学生进行综合搭配并分为8个小组，每一小组在一个圈子里面，由小组长负责协调并分配相关任务，这样便于讨论与交流，使能力相对较差的学生能够迅速提高。各小组成员的作品存放在指定的位置，便于小组自评并推荐小组最佳作品参与互评，从而评出课堂最佳。
五、课时安排
1课时
六、媒体准备
多媒体教学平台、网络电子教室
七、教学过程
引入：同学们，上一节课我们学习了顺序查找的方法。请小组内讨论一下：
[游戏1]：
现在有50个小圆球，其大小、颜色等完全相同，其中有一个小球比其它49个小球重5克，现给你一天平（无具体刻度），要求将该小球找出来，我们该怎么办？
[设计意图]：通过小组讨论与交流，部分小组认为两两比较，这种方法可以解决问题。教师追问：不管较重的小球在什么位置，我们能不能用更少的次数
找出小球？有小组能够想到：先将50个球分为两分（每25个一分），分别放到天平左右两个托盘中，如果，左则重，将左则球分为两等分（每分12个球），再将这两部分别放到天平的左右两则，如果左右两则平衡，则另一小球就是我们要找的小球，如果不等，再将重的一侧分为两分，以此类推，就能很快找到小球。（不管小球在何处，都能在5步以内找到该小球）
[游戏2]：
请一个同学到前台配合玩一个关于价格竞猜的小游戏，给大家展示一个物品，告诉大家价格大概的范围（100元-400元），同时告诉上来的同学具体价格，另一同学竞猜，上来的同学根据实际价格和学生报价给出提示：“高了”、“低了”、“正确”。
[设计意图]：这一游戏实际上中央电视台一个节目，给你一商品的价格范围，让你在规定的时间内猜出它的价格。只要我们采用“二分法”去猜，就能很快的猜出它的价格。这两游戏和学生的编程思想是紧密相连的，所以游戏的导入一方面是引起学生学习的热情，另一方面也是让学生领会编程设计方法：二分法。为下面教学活动的开展做好铺垫。
[提出问题]：
请同学们思考，这位同学通过什么方法比较快速的猜出实际价格的呢？
[引出课题]：
二分法查找
[提出问题]：
二分法查找究竟是怎样查找的呢？它的实现有没有什么条件呢？请大
家阅读课本P54-55，小组内讨论这两个问题。
[新课讲解]：
二分法查找的条件是被查数据是有序的，否则无法使用二分法查找。 那二分法查找是怎样查找的呢？现在这一物品价格为260元，通过二分法怎样查找？
[学生回答]：
首先将100设置为下界，400设为上界，然后取上下界的中间元素250与指定的值260进行比较，由于250比260小，所以250左则的数据舍弃，然后把250作为下界，取上下界的中间元素325与260进行比较，由于325比260大，所以舍弃325右则数据，再将325作为上界，取上下界的中间元素比较，以此类推，就能很快找到。
[教师]：
有没有哪一组的同学进行补充？
[学生补充]：
由于中间元素250比指定值260小，所以250不符合要求，就该将251作为下界，同样，由于325比260大，也不符合要求，应将324作为上界，这样能够减少查找次数。
[教师分析、讲解]：
很好。虽然上下界在中间元素上加减1，但如果查找的数据较多，这样就可以提高查找效率，另外从算法的角度出发，我们就应该考虑到这些问题。
我们首先要设置下界low=100，上界high=400,取中间元素mid=(low+high)\2，mid=250，比260小，左则舍弃，取mid 右则数据作为low ，即low=mid+1，再取mid=(low+high)\2，比260大，右则舍弃，取mid 左则数据
作为high ，即high=mid-1，以此类推，如找到，则结束。
教师再播放一flash 动画，帮助学生进一步理解二分法算法。
师生一起共同分析流程图并写出“大了”或“小了”部分代码。
刚才我们是请同学猜价格，那我们现在就让计算机来猜猜。
教师在学生小组自评和小组互评的基础上评出最佳小组和最佳个人。同时，学生在完成任务的过程中，教师特别要留意程序编写过程中出现错误的同学，在总结的过程中指出问题所在，促进学生提高编程能力。
[教师课堂总结]
前面一节课我们学习了顺序查找，如果查找的数据较多或频繁进行查找，顺序查找效率会比较低，而使用二分法查找则可以提高查找的效率。而二分法查找的数据是有序的，怎样让一组无序的数据变成有序的，便于我们通过二分法查找呢，下节课我们将一起来探讨这一问题。
参考文献:普通高中课程标准实验教材《算法与程序设计（选修）》教师教学用书
教育科学出版社
二分法查找教学设计
江苏省东台中学 朱世华
一、教学课题
第三章第三节《二分法查找》——算法与程序设计（新课标教科书；教育科学出版社）
二、教材及学者分析
《二分法查找》这部分知识在新课程数学必修1中已经涉及到，在前面的知识中，学生基本掌握数组的简单应用，并且已经能够利用顺序查找方法对某个数据队列进行单个数据查找。本节课主要让学生掌握二分法查找的基本思想，并将这一算法体现到具体的实例中，从而提高解决问题的效率。
三、教学目标
1、认知目标
理解二分法查找算法的基本思想。
2、技能目标
掌握二分法查找算法的简单应用（编写猜数小游戏）。
3、情感目标
培养学生的自主学习、互相协作、分析问题的能力。
4、教学重点
二分法查找算法的理解。
四、教法与学法
1、教法：任务驱动法、范例教学法、情境教学法
2、学法：自主式学习、互助式学习
说明：开课请同学参与完成两游戏，这两游戏和学生的编程思想是紧密相连的，所以游戏的导入一方面是引起学生学习的热情，另一方面也是让学生领会编程设计方法：二分法。为下面教学活动的开展做好铺垫。根据学生接受知识的能力不同，将学生进行综合搭配并分为8个小组，每一小组在一个圈子里面，由小组长负责协调并分配相关任务，这样便于讨论与交流，使能力相对较差的学生能够迅速提高。各小组成员的作品存放在指定的位置，便于小组自评并推荐小组最佳作品参与互评，从而评出课堂最佳。
五、课时安排
1课时
六、媒体准备
多媒体教学平台、网络电子教室
七、教学过程
引入：同学们，上一节课我们学习了顺序查找的方法。请小组内讨论一下：
[游戏1]：
现在有50个小圆球，其大小、颜色等完全相同，其中有一个小球比其它49个小球重5克，现给你一天平（无具体刻度），要求将该小球找出来，我们该怎么办？
[设计意图]：通过小组讨论与交流，部分小组认为两两比较，这种方法可以解决问题。教师追问：不管较重的小球在什么位置，我们能不能用更少的次数
找出小球？有小组能够想到：先将50个球分为两分（每25个一分），分别放到天平左右两个托盘中，如果，左则重，将左则球分为两等分（每分12个球），再将这两部分别放到天平的左右两则，如果左右两则平衡，则另一小球就是我们要找的小球，如果不等，再将重的一侧分为两分，以此类推，就能很快找到小球。（不管小球在何处，都能在5步以内找到该小球）
[游戏2]：
请一个同学到前台配合玩一个关于价格竞猜的小游戏，给大家展示一个物品，告诉大家价格大概的范围（100元-400元），同时告诉上来的同学具体价格，另一同学竞猜，上来的同学根据实际价格和学生报价给出提示：“高了”、“低了”、“正确”。
[设计意图]：这一游戏实际上中央电视台一个节目，给你一商品的价格范围，让你在规定的时间内猜出它的价格。只要我们采用“二分法”去猜，就能很快的猜出它的价格。这两游戏和学生的编程思想是紧密相连的，所以游戏的导入一方面是引起学生学习的热情，另一方面也是让学生领会编程设计方法：二分法。为下面教学活动的开展做好铺垫。
[提出问题]：
请同学们思考，这位同学通过什么方法比较快速的猜出实际价格的呢？
[引出课题]：
二分法查找
[提出问题]：
二分法查找究竟是怎样查找的呢？它的实现有没有什么条件呢？请大
家阅读课本P54-55，小组内讨论这两个问题。
[新课讲解]：
二分法查找的条件是被查数据是有序的，否则无法使用二分法查找。 那二分法查找是怎样查找的呢？现在这一物品价格为260元，通过二分法怎样查找？
[学生回答]：
首先将100设置为下界，400设为上界，然后取上下界的中间元素250与指定的值260进行比较，由于250比260小，所以250左则的数据舍弃，然后把250作为下界，取上下界的中间元素325与260进行比较，由于325比260大，所以舍弃325右则数据，再将325作为上界，取上下界的中间元素比较，以此类推，就能很快找到。
[教师]：
有没有哪一组的同学进行补充？
[学生补充]：
由于中间元素250比指定值260小，所以250不符合要求，就该将251作为下界，同样，由于325比260大，也不符合要求，应将324作为上界，这样能够减少查找次数。
[教师分析、讲解]：
很好。虽然上下界在中间元素上加减1，但如果查找的数据较多，这样就可以提高查找效率，另外从算法的角度出发，我们就应该考虑到这些问题。
我们首先要设置下界low=100，上界high=400,取中间元素mid=(low+high)\2，mid=250，比260小，左则舍弃，取mid 右则数据作为low ，即low=mid+1，再取mid=(low+high)\2，比260大，右则舍弃，取mid 左则数据
作为high ，即high=mid-1，以此类推，如找到，则结束。
教师再播放一flash 动画，帮助学生进一步理解二分法算法。
师生一起共同分析流程图并写出“大了”或“小了”部分代码。
刚才我们是请同学猜价格，那我们现在就让计算机来猜猜。
教师在学生小组自评和小组互评的基础上评出最佳小组和最佳个人。同时，学生在完成任务的过程中，教师特别要留意程序编写过程中出现错误的同学，在总结的过程中指出问题所在，促进学生提高编程能力。
[教师课堂总结]
前面一节课我们学习了顺序查找，如果查找的数据较多或频繁进行查找，顺序查找效率会比较低，而使用二分法查找则可以提高查找的效率。而二分法查找的数据是有序的，怎样让一组无序的数据变成有序的，便于我们通过二分法查找呢，下节课我们将一起来探讨这一问题。
参考文献:普通高中课程标准实验教材《算法与程序设计（选修）》教师教学用书
教育科学出版社