高中二年级信息技术选择性必修1查找算法的程序实现教学设计

高中二年级信息技术选择性必修1查找算法的程序实现教学设计教学内容分析本课内容选自浙教版高中信息技术选择性必修1《数据与数据结构》第五章第四节“查找算法的程序实现”第二课时。前一课时学生已经掌握了顺序查找的基本思想，能够用循环结构遍历列表并完成目标元素的定位，理解了查找成功与查找失败两种情形的程序表达方式。本课时在此基础之上引入二分查找，引导学生经历“问题提出—思想感悟—算法设计—程序实现—效率比较—迁移应用”的完整探究过程。《普通高中信息技术课程标准》在模块“数据与数据结构”中明确要求学生理解常用查找算法的基本思想，能够用程序实现简单查找算法，并能结合具体问题对算法效率进行分析比较。本课时正是落实该要求的关键节点。二分查找不仅仅是一个算法知识点，更承载着计算思维培养的核心价值：它体现了“分治”与“降规模求解”的通用策略，其思想将在后续的排序算法、递归概念乃至数据索引结构中反复出现。因此本课的设计不以“会默写代码”为终点，而以“理解为何快、知道何时用、能够自己写”为目标。学情分析授课对象为高二年级学生，已完成必修课程学习，具备Python基本语法基础，包括列表、循环、条件判断和函数定义，前一课时已实现顺序查找并实测了不同规模数据下的查找次数。学生的优势在于：能读懂逐一遍历的代码，能通过运行观察输出结果，对“次数对比”类实验有兴趣。学生的困难集中在三个方面：其一，容易把二分查找理解成“死记代码”，不清楚mid=(low+high)//2背后的区间收缩逻辑；其二，循环边界条件low<=high与low、high的更新方式（mid加一或减一）容易混淆，写出的程序常出现死循环或漏查边界元素；其三，对“前提条件——数据必须有序”缺乏敏感性，容易在无序数据上直接套用。教学中需要设置足够的可视化支架与错误样例辨析活动。教学目标信息意识：通过大规模数据查找情境，感知数据规模扩大时算法选择对程序性能的决定性影响，形成“先分析数据特征、再选择算法”的意识。计算思维：理解二分查找通过每次将查找区间减半来缩小问题规模的基本思想，能借助变量low、high、mid用自然语言和流程方式描述算法过程，能将区间收缩的重复结构抽象为循环。数字化学习与创新：用Python编写并调试二分查找程序，通过增加计数变量实测比较两种查找在十万级、百万级数据下的最不利查找次数，用实验数据支撑算法优劣的判断，尝试用递归方式实现同一算法并比较两种实现。信息社会责任：认识到教科书般严谨的算法必须以正确性为前提，在程序设计中养成边界测试的习惯，理解“聪明的算法节省算力就是节约能源”的工程伦理内涵。教学重点与难点教学重点：二分查找的基本思想与Python程序实现；查找区间收缩过程的变量变化规律。教学难点：循环条件与边界更新的正确理解；二分查找以数据有序为前提这一适用条件；平均查找次数对数级增长的定量感悟。教学准备硬件环境：机房一人一机，Python3.x环境，教师机装有屏幕广播软件。软件素材：教师提前准备三个半成品文件——名为bingame.py的猜数游戏（教师演示用）、名为binary_framework.py的二分查找代码框架（留有空缺）、名为pare.py的效率对比实验脚手架。另准备一打纸质卡片，写有1至13共十三个有序数字，供学生手工模拟。前测连接：要求学生课前复习上一课顺序查找代码，能独立默写核心三行结构。教学过程一、情境导入：猜数游戏中的智慧（约6分钟）教师课前布置一个小约定：教师在心中想一个1到100之间的整数，请学生提问，教师只回答“大了”“小了”或“猜对了”，比一比哪个小组用最少的问题猜中。学生哄然而动。第一个学生往往从“是不是50”开始，教师答“大了”，区间立刻减半为1到49；第二问“是不是25”，答“小了”，区间收缩为26到49……七个问题之内必然命中。教师追问：为什么五十次以内任意一个数，七个问题就一定能找到？学生口答“每次排除一半”。教师顺势在黑板上写出计算：100要减半几次变到1？用算盘式口算：100、50、25、13、7、4、2、1——至多七次。再抛出问题：一百万呢？学生用计算器按，约二十次。数据的反差在教室里造成直观的震撼——从“要查一百万次”到“只要二十次”，不是靠运气，而是靠方法。教师点题：刚才大家不知不觉已经使用了计算机科学中最经典的算法之一——二分查找。今天我们把它从游戏变成程序。板书课题：5.4查找算法的程序实现（二）——有序数据的二分查找。设计意图：用人人可参与的游戏激活已有经验，用数量级差距制造认知冲突，让“为什么要学”先于“怎么写”发生。同时暗示前提条件——猜数之所以能排除一半，是因为老师诚实地给出了大小关系，相当于数据天然有序。二、情境反诘：如果数据乱序呢（约4分钟）教师提出反例：假如老师犯规，每次随机撒谎，你还敢每次排除一半吗？学生很快意识到不行。教师类比：如果我要在一份乱序的名单中找一位同学，能不能看中间一个人的名字后直接扔掉一半？学生判断不能。由此归纳出二分查找的第一条铁律：被查找的数据必须有序（升序或降序均可）。教师展示两张幻灯片：一张为有序名单适用二分，一张为无序名单只能顺序扫描。请学生用自己的话补充第二条前提：如果数据原本无序而建索引或排序后需要反复查找，先排序再二分仍是划算的；若只查找一次，顺序查找更省事——算法选择取决于使用场景。设计意图：正面讲授之前先制造“反例冲击”，让学生在概念形成之初就把适用条件纳入心智模型，避免后续机械化套用。三、手工模拟：十三张卡片中的区间之旅（约8分钟）每组领取十三张数字卡片（1至13），按升序摊开在桌面上。任务：从1数起每个数占一个位置，位置编号记为0至12，目标数为7。要求按二分规则操作，并在记录表中逐步填写每一轮的low、high、mid三个位置值与比较结果。学生动手：第一次查找区间是0到12，中点位置为6，卡片上数字是7，恰好命中。教师再指定目标数13让各组重来：第一轮中点6处是7，比13小，答案只能在右半边，于是low变为7，区间7到12；中点9处是10，仍小，low变为10……直到命中。教师巡视时重点观察：low和high的取值是否随轮次正确更替；mid取整方式是否与“中间偏左”一致。完成最快的小组被请到讲台，用大屏卡片演示，并解释“为什么这次mid加一赋值给low，而不是直接赋mid”——因为mid位置的元素已经比较过且不是目标，继续包含它只会白费一轮甚至死循环。小结黑板呈现三条口诀：求中点，比一比；比就大，缩左半，high放到mi­d左边；比就小，缩右半，low放到mi­d右边；相等即命中，返回中点位置。设计意图：程序执行的关键在于变量的动态演化。卡片操作把抽象的下标变化变成手边的物理移动，为代码环节扫清最顽固的障碍。这一环节也天然罗列了教学难点的核心——边界更新规则。四、算法描述与框架搭建（约6分钟）教师引导学生把刚才的手部动作翻译成结构化语言。师生共同完成如下伪代码（直接展示于投影）：当low不超过high时反复执行：让mid等于(low加high)的整除一半若a[mid]恰好等于目标key，返回mid并结束若a[mid]小于key，说明目标在右侧，low更新为mid加一否则目标在左侧，high更新为mid减一循环结束后仍未命中，说明目标不存在，返回减一教师提问逐层递进：循环终止条件为什么写low小于等于high，而不是严格小于？请学生思考区间只剩一个元素即low等于high的情形——若用小于则该独一无二的候选元素被跳过，造成漏查。学生通过代入具体数值验证后心服口服。再问：如果区间内没有元素了，即low跑到了high右侧，意味着什么？学生答：查找失败，目标不在列表中。由此自然引出返回值约定：成功返回下标，失败返回减一。设计意图：伪代码是自然语言与程序之间的桥梁；对临界条件的追问，让学生在写代码前先“想清楚”，把常见错误消灭在编写之前。五、程序实现：从框架到可运行代码（约12分钟）学生在教学平台半成品框架，文件内容如下（留空处以注释标记）：defbinary_search(a,key):low=0high=len(a)1whilelow<=high:mid=(low+high)//2ifa[mid]==key:returnmidelifa[mid]<key:low=mid+1else:high=mid1return1教师布置三个递阶任务。任务一：补全框架并运行测试集。测试数据为列表[3,7,12,18,23,29,35,41,46,52]，依次查找29、3、52、100，预期输出下标5、0、9、1。学生独立完成，通读报错信息并相互校对。任务二：加计数器，观察每轮区间。要求在循环开始处增加打印语句，输出每一轮的low、mid、high值，手工核对与卡片模拟结果是否完全一致。学生发现代码运行轨迹与自己的手算完全一致，成就感明显。任务三：故意出错，学会排错。教师故意演示：把low=mid+1误写为low=mid，运行“在一至十中查11”的程序，观察现象——程序无休止地打印同一区间。请学生分析死循环成因，并给出修正。随后再演示另一处常见错误：把low<=high写成low<high，在单元素区间处漏查。这两个经典错误直接来自学生上一环节手工模拟的盲区，集体诊断后印象深刻。中段小结提炼板书：三个变量、一个循环、三种分支、一条铁律（数据有序）。教师同时提醒一个工程细节：当数据量极大时，(low+high)//2在某些语言中可能溢出，Python的整数不受限，但养成写low+(highlow)//2的习惯更好，供学有余力者探究。设计意图：任务分层覆盖“能写、能看懂、能排错”三个层级；错误样例源于学情预判，以演示—诊断—修正的方式完成难点突破。整节课对关键代码实行“先讲清、再补写、后纠错”，避免学生直接抄写。六、效率实测：用数据说话（约10分钟）教师分发实验脚手架pare.py，其中已写好生成升序列表的函数与两种查找函数（顺序查找沿用上一课成果），均由学生调用并统计比较次数。实验设计如下：数据规模分别取一千、一万、十万、一百万；目标统一设为不存在的最大数（构造最不利情形）；分别记录顺序查找与二分查找的比较次数并填入实验记录表：规模一千：顺序一千次，二分约十次。规模一万：顺序一万次，二分约十四次。规模十万：顺序十万次，二分约十七次。规模一百万：顺序一百万次，二分约二十次。学生运行后目睹反差：当数据飙升一百万倍，二分查找的比较次数只翻了一倍。教师引导数学化表述——二分查找的最不利比较次数约等于以2为底、数据量加一为真数的对数向上取整，在屏幕上以可视化方式呈现为：次数≈⌈log₂(n+1)⌉。同时给出时间复杂度的量级称呼：顺序查找为线性级，二分查找为对数级。教师再追问三个辨析问题，全班快速作答：一、如果列表只有十个元素，二分还明显占优吗（优势不明显，但思想一致）；二、如果数据无序且只查一次，为何不能先排序再二分（排序本身的代价超过一次顺序查找）；三、现实世界里什么系统在每秒做数以亿计的“二分”思想（搜索引擎索引、字典树检索、数据库B+树——其灵感即来自多路二分）。设计意图：把“快”从口号变成数字。实验用极端规模制造冲击，数学化表达使学生初识复杂度概念，为后续选修内容埋下伏笔；三个辨析问题促使学生形成场景化的算法选择观。七、拓展提升：递归的另一种表达（约6分钟）教师提出问题：二分查找每轮做的事情，能不能用“自己调用自己”的方式来写？在黑板上与学生共同构造递归版本：defbs(a,key,low,high):iflow>high:return1mid=(low+high)//2ifa[mid]==key:returnmidelifa[mid]<key:returnbs(a,key,mid+1,high)else:returnbs(a,key,low,mid1)师生对照两种实现，归纳：循环版靠区间变量驱动，递归版靠参数传递新区间；二者本质相同，出口条件一致。教师布置思考：递归层数最多是多少？学生联系对数结论答出约log₂(n)层。设计意图：同一算法的双实现让学生体会“循环与递归等价”的高阶结构观，为第六章递归学习预热；此环节对学优生留白，对大多数学生只要求读懂。八、回归应用：算法之外的眼光（约4分钟）教师呈现两个真实场景让学生判断与献策。场景一：学校机房一百万条学生活动日志需按学号检索记录，应当如何组织数据、采用何种算法？学生答：先按学号排序或建索引，再二分。场景二：体检中心排队叫号显示屏按姓氏查找病历，数组每来一位新人都乱序怎么办？讨论后明确：动态数据适合哈希或树形结构，那也是后续课程的方向。教师总结方法论的层次：第一步永远问“数据有序吗、查几次”；第二步才谈算法选择；第三步是正确性验证，用空列表、单元素、目标不存在、目标在边界四类用例做最简测试。学生在笔记本上记录这一决策口诀。设计意图：把“会写一段代码”提升为“会做一个决策”，体现学科核心素养由知识层面向方法层面的迁移。九、课堂小结（约3分钟）由学生接力完成“三句话总结”：第一句，二分查找为什么快——每次排除一半；第二句，它的前提和代价——数据须有序，写错边界易死循环；第三句，它的数量级——对数级，百万数据不过二十次。教师在黑板上勾连知识脉络图：问题情境—思想—伪代码—循环实现—递归实现—效率比较—应用场景，一个闭环清晰可见。十、作业布置（分层）基础层：完成教材配套练习中关于二分查找的三道题，要求其中一题手绘查找过程表（逐轮写出low、mid、high）。提高层：改造课堂程序，使其在查找失败时不返回减一，而是返回目标若插入应保持有序的正确位置（这正是Pythonbisect模块的功能），并自行构造五组测试验证。挑战层：阅读资料或自行推导，用while循环实现猜数游戏的“出题方”——计算机猜用户想的数，要求不超过六次猜中一至一百内的数，下节课展示。板书设计主板书自左向右依次呈现：课题；三条口诀（求中点、比大小、缩区间）；核心代码骨架；效