高中一年级信息技术《二分法查找的算法构建与程序实现》教学设计

高中一年级信息技术《二分法查找的算法构建与程序实现》教学设计一、教学背景分析本课选自高中信息技术选择性必修模块"算法与程序设计"中"查找算法"单元的核心内容，面向江苏省海安高级中学高一年级选修该模块的学生开设。学生在此之前已经完成了顺序结构、分支结构、循环结构三种基本控制结构的学习，能够使用Python编写简单的程序解决累加、枚举类问题，对数组（列表）这一数据结构有了初步认识，也刚刚学完顺序查找的基本思想。二分法查找是学生接触的第一个体现"算法效率"差异的典型案例，是从"会写程序"走向"写好程序"的关键一课。从学情来看，学生在数学学习中接触过函数的零点问题，对"区间缩小"的朴素思想并不陌生，但将这种直觉经验转化为精确的、可由计算机执行的算法描述，仍是一道明显的认知鸿沟。特别容易出错的地方集中在三处：一是查找区间边界的更新规则，结束位置究竟是mid还是mid1；二是循环终止条件的确定，究竟是low小于high还是low小于等于high；三是对"有序"这一前提条件的忽视，部分学生会直接对无序数据套用二分查找而不自知。这些易错点恰恰是本课最有价值的教学资源。依据普通高中信息技术课程标准对"计算思维"核心素养的要求，本课将目标定位在：让学生经历"问题情境—数学抽象—算法设计—程序实现—效率分析—迁移应用"的完整过程，理解二分查找每次将搜索范围减半的机制，能正确写出边界处理的代码，并通过对比实验体会算法时间与问题规模之间的对数关系。二、教学目标知识与技能层面，学生能够用自己的语言描述二分查找的适用前提和基本步骤，能用自然语言、流程图两种方式表达算法，能独立写出边界处理正确的Python实现代码，并能口头说明每一步边界更新的理由。过程与方法层面，学生通过"猜数游戏"的亲身体验归纳出折半策略，通过手工模拟小规模数据的查找过程发现并修正边界错误，通过对不同规模数据的计时实测建立对数阶效率的直观感受。情感态度与价值观层面，学生在对一亿个数据"最多比较27次"这一事实的震撼中，体会算法设计的力量，形成"先分析、再动手"的工程习惯，初步建立用数据说话、用实验验证的科学态度。三、教学重点与难点教学重点是二分查找算法的思想理解与程序化实现，即"定区间、取中点、作比较、缩范围"这一循环不变式的建立。教学难点有二：其一是循环终止条件与边界更新的配合关系，即whilelow<=high与low=mid+1、high=mid1之间的内在逻辑一致性；其二是算法效率的定量理解，让学生真正相信log₂n次比较的量级含义，而不是死记结论。突破策略是：用"猜数字"游戏建立直觉，用"纸上追踪三数据、十数据"暴露错误，用"修改—运行—再修改"的调试循环修正认知，用"规模翻十倍、次数加几"的实验数据完成对效率的论证。所有结论尽量让学生先说、先写、先错、先改，教师只做方向的把控与关键处的点睛。四、教学方法与课前准备教学方法采用情境驱动法、任务驱动法与实验探究法相结合，辅以同伴互查。课前准备包括：机房内每台机器安装Python运行环境与代码编辑器；教师准备好三个递进的程序半成品文件（分别对应游戏版、基础版、统计版）；准备一张打印好的"二分查找手工追踪单"，上面印有一个含十六个元素的有序列表和待填写的low、high、mid追踪表格；教室多媒体可投屏演示。五、教学过程环节一：游戏导入，直觉先行（约8分钟）上课伊始，教师不打开任何课件，只说一句话："我心里想了一个1到100之间的整数，你们来猜，我只回答'大了'或'小了'，看看全班最少几次能锁定答案。"学生踊跃猜数。第一轮，一个学生从50开始猜，根据提示逐次折半，七次之内猜中。教师追问："为什么是七次？谁来说说刚才的策略？"学生回答中自然出现"每次砍掉一半"这样的表述。教师板书四个词：定区间、取中点、作比较、缩范围。接着提出挑战："如果是1到100万之间的一个数呢？"多数学生凭刚才的经验估算二十次左右。教师不急于肯定，布置心算任务：100万连续除以2，除多少次会小于1？学生很快得出二十次左右足矣的结论，课堂气氛为之一振。教师顺势点题："这个策略有个正式的名字——二分法查找，也叫折半查找。今天我们要做的不只是会玩这个游戏，而是把这个策略变成一段计算机能不折不扣执行的程序，并弄清楚它凭什么这么快。"设计意图是：算法的种子必须生长在学生的直觉土壤里，而不是从教师的嘴里空降。猜数游戏在心理上完成了"折半策略"的第一次建构，同时"一百万只要二十次"的悬念为后面的效率分析埋下伏笔。环节二：从游戏到算法，明确前提与规则（约8分钟）教师提出问题链，逐层推进。第一个问题："把猜数游戏换成计算机语言，要告诉计算机哪几样东西？"学生讨论后归纳出：一个排好序的数列、一个待查找的目标值、区间的两个端点。教师强调"排好序"三个字，随手在黑板上写出一组乱序数据如8、2、15、6、30、11，问："对这个数列，还能直接折半吗？"学生意识到砍掉一半的前提是知道目标在哪个半区，而这依赖于有序性。至此，二分查找的第一前提"数据有序"由学生自己说出口。第二个问题："区间的两个端点在程序里用什么表示？"结合学生已有的列表索引知识，确定用low和high两个变量分别记录当前查找区间的起始下标和结束下标，初始时low为0，high为len(a)1。第三个问题："中点怎么算？"学生给出mid=(low+high)//2，教师追问为什么用整除，学生联系索引必须为整数回答，完成细节落实。第四个问题最关键："比较之后，区间怎么缩？"教师请三名学生上黑板，分别写出目标值大于、等于、小于中点元素三种情况下low和high的新值。此处必现错误：有学生写成low=mid、high=mid。教师不立即纠正，而是说："先记下你们的版本，待会儿我们让数据来审判它。"设计意图是：把算法规则的每一条都变成学生必须回答的问题，而错误版本的出现是意料之中的教学设计——它为下一环节的调试冲突准备了弹药。环节三：手工追踪，暴露边界错误（约10分钟）学生拿出追踪单，面对十六个元素的有序列表[3,7,11,15,19,22,26,31,35,40,44,48,52,57,61,66]，任务是查找目标值11。学生用空格笔逐轮填写追踪表：第一轮low=0、high=15、mid=7，a[7]为31，大于11，区间缩到左半，high变为mid1即6；第二轮low=0、high=6、mid=3，a[3]为15，仍大于11，high变为2；第三轮low=0、high=2、mid=1，a[1]为7，小于11，low变为mid+1即2；第四轮low=2、high=2、mid=2，a[2]为11，命中，共比较四次。完成正确版本的追踪后，教师抛回上一环节悬置的问题："现在回看刚才黑板上low=mid的错误版本，会出什么事？请用这个数据验证。"学生代入发现：当low与high相等且不命中时，若写low=mid，则low不增、high不减，区间永远缩不动，程序陷入死循环。接着验证high=mid的版本，同样会在两元素相邻的特殊状态下卡死。对比之下，"加一减一"的必要性不言自明。教师在此提炼一句话请学生记在书上："mid这个位置已经比较过了，它出局了，新区间必须把mid排除在外。"紧接着追问终止条件："循环什么时候停？"学生从刚才第四步low=high=2的情况出发，讨论出即使只剩一个元素也必须再比较一次，因此条件应为low<=high而非low<high；若写成小于，恰好落在最后一个元素上的目标就会被漏检。教师请学生举例验证：查找列表中的57，会出现在low=high的状态，用错误条件则提前退出，报告"未找到"，而数据明明就在眼前。设计意图是：边界问题是本课最大的坑，纸上追踪让学生在零风险环境里先摔一跤，"数据审判决"比教师讲解任何正确的代码都有说服力。这也呼应了课程标准中"通过剖析典型案例理解算法"的要求。环节四：程序实现与调试（约12分钟）学生打开基础版半成品文件，框架已给出，核心部分留空，要求独立完成补全：defbinary_search(a,target):low=0high=len(a)1whilelow<=high:mid=(low+high)//2ifa[mid]==target:returnmidelifa[mid]<target:low=mid+1else:high=mid1return1教师巡视中重点关注三类典型错误并即时点拨：第一类是把终止条件写成low<high的学生，引导他用十六元素列表查找最后一个或第一个元素来测试，程序返回1的意外结果会立刻让他警觉；第二类是边界写成low=mid的学生，程序运行时卡住无响应，教师提示用Ctrl+C中断后思考"哪一步区间没缩小"；第三类是mid用了普通除法导致类型错误的学生，通过阅读报错信息自行修正。完成基础版后，进入测试环节。教师给出三条测试用例设计原则并请学生互相出题：要测"存在且在中间"的目标，如26；要测"存在且在两端"的目标，如3和66——这是专杀边界错误的用例；要测"不存在"的目标，如10，确认程序正确返回1且不死循环。学生两两结对，一人出题一人运行，再交换角色，完成第一次同伴互查。教师点评时强调一个工程习惯："一段只在你想过的情况下正确的代码，不算正确的代码。测试用例的覆盖面，决定了你对程序的信任程度。"设计意图是：补全式编程既降低了语法门槛，又把认知负荷集中到算法逻辑本身；三类错误的预判来自多年课堂观察，巡视中的精准点拨才能发生时测试用例的互相设计与执行，是把"调试"从纠错行为升格为验证习惯的载体。环节五：效率实验，见证"logn"的震撼（约10分钟）教师发放统计版半成品，其中在binary_search函数中加入计数变量count，每次比较后加一，函数返回比较次数。同时提供另一份顺序查找的计数版本作对照。实验任务分三步。第一步，生成规模分别为1000、10000、100000、1000000的有序列表，分别用两种算法查找"最后一个元素"这一最坏情形，记录比较次数并填入表格。学生很快得到：顺序查找的次数等于元素个数，而二分查找依次约为10、14、17、20次。第二步，计算验证。学生用计算器求各规模的log₂值：log₂1000约9.97，log₂1000000约19.93，与实测次数完全吻合。教师板书结论："二分查找的最坏比较次数约为log₂n加上不超过1的修正，时间复杂度记作O(logn)。"第三步，直观感受。教师提问："如果有十亿个数据，大约要比较多少次？"学生算出约30次。教师给出现实换算："假设每做一次比较花一微秒，顺序查找最坏要一千秒，约十七分钟；二分查找只要三十微秒，眨眼之间。同一份数据，同一台电脑，差的不是硬件，是算法。"教室里出现真实的惊叹声，这是算法课最珍贵的时刻。教师再补一刀深化理解："反过来，每次比较就把问题规模砍掉一半，所以规模翻倍，次数只加一。「指数爆炸」的反面，就是「对数收敛」。"设计意图是：效率概念不能靠背诵，必须靠数据。学生亲手跑出来的对照表和亲手算出的对数值，共同构成O(logn)的证据链。"十亿个数据三十次"的换算则是把抽象数学翻译成情感体验的临门一脚。环节六：迁移拓展与课堂小结（约7分钟）教师展示三个真实场景请学生判断二分思想是否适用。场景一：字典里查一个英文单词。学生立刻联想到按字母序翻页折半，答案肯定。场景二：一本被打乱顺序的弹夹编号中查找某编号。学生明确回答不行，因为无序，除非先排序，顺势引出"排序成本与查找收益的权衡"这一伏笔，为后续排序算法教学埋下钩子。场景三：monitor279元、280元、281元三种标价商品中找280元的那件，学生笑着指出三次数据折半并不比逐个看快，规模太小体现不出优势——这说明了算法的适用范围意识。接着布置分层作业：基础层，完成教材配套练习中查找旋转点之前的有序数组查找题，并手画追踪表；提高层，修改程序，使其能统计并输出查找过程中访问过哪些下标，即画出查找路径；挑战层，思考并尝试实现"在一个先升后降的山形数组中寻找峰值"的问题，提示可以用二分思想但不能照搬。课堂收束时，教师请三名学生各用一句话总结今天的收获，教师最后凝练三句话写在黑板中央："二分查找的前提是秩序；二分查找的灵魂是区间；二分查找的价值是用智慧的次数换笨拙的规模。"六、板书设计主板书区域自上而下呈现：课题"二分法查找"；"四步法"——定区间、取中点、作比较、缩范围；前提条件"数据有序"；核心代码框架（whilelow<=high及其内部三分支）；效率结论"次数约等于log₂n，十亿数据约三十次"。副板书区域用于记录学生初始的错误版本与修正过程，保留思维的痕迹，这是本堂课上过的证据。七、作业设计说明作业呈三层梯度，基础层保证人人过关算法主干，提高层训练追踪与表达能力，挑战层为学有余力的学生打开变式应用的窗口。所有作业均要求附一句"我验证过我的程序"的自查说明，列出自己使用的测试用例，把验证意识延伸到课外。八、教学评价设计本课采用过程性评价与结果性评价结合的方式。过程性评价关注三个观测点：手工追踪单的正确率反映算法理解程度，结对测试中出错的案例质量反映批判性思维水平，实验数据表格的完整度反映实证态度。结果性评价以课后分层作业的完成质量为依据。评价主体上，教师评价与同伴互评并行，追踪单在小组内先互改再交教师复核。九、教学反思预设从往届实施情况看，