高中信息技术选择性必修1顺序查找与二分查找程序实现教案

高中信息技术选择性必修1顺序查找与二分查找程序实现教案一、教学内容定位本课属于高中信息技术选择性必修1“数据与数据结构”模块中“查找算法的程序实现”起始课时，承接数组、循环结构、条件判断、函数封装等已有知识，指向“用计算机方式解决问题”的核心经验。学生已经能够把现实问题抽象成数据表，也能写出遍历列表的基本代码，但对“查找”往往停留在眼睛扫视的生活经验，缺少对查找范围、比较次数、终止条件、结果返回方式的精确描述。本课以顺序查找为入门模型，以二分查找为效率跃迁点，让学生在可运行、可测试、可比较的代码中理解算法思想，而不是背诵流程。教材将查找安排在排序之后、更复杂数据结构之前，意图十分明显：数据只有被组织起来，查找才可能从“逐个看”走向“按规则缩小”。顺序查找承认数据无序也能完成任务，体现通用性；二分查找要求数据有序，体现结构对算法效率的制约。二者并置，能帮助学生建立“问题条件决定算法选择”的判断框架。课堂不追求花哨情境，而把力度放在三个可检验点上：目标值在不在、找到了返回什么、找不到如何交代。二、学情研判授课对象为高中二年级选修本模块的学生，思维已经具备形式化倾向，但程序实现常会输给细节。常见困难有四类：一是循环边界写成range(len(a))与range(len(a)1)时凭感觉改动；二是把“找到立即返回”与“循环结束后再判断”混在一起，导致结果覆盖；三是理解二分查找时会说“取中间”，却写不出left、right、mid的同步更新；四是把有序当成装饰条件，忽视二分查找前提是序列已经按键值排好。课堂需要通过小步运行、变量追踪和错误对照，让学生看到每一次比较如何改变可能区域。学生差异也较明显。基础较弱学生能模仿顺序查找，却在返回值设计上摇摆；能力较强学生会追问平均比较次数、最坏情况、重复元素处理。教学采用同一任务三层输出：能跑通、能解释、能优化。评价不看谁背得快，而看谁能用数据说明自己算法为什么停止、为什么正确、为什么更快。三、教学目标学生能用自然语言、流程描述和Python代码三种方式表达顺序查找，明确输入、输出、循环不变量与终止条件；面对长度为n的列表，能说出最坏比较n次、找到即停止的实现要领，并用测试用例验证存在、不存在、位于首端、位于末端四种情形。学生能在有序序列上实现二分查找，正确维护左边界left、右边界right、中间位置mid，理解mid=(left+right)//2的可视含义，能解释每一轮比较后为什么可以舍弃一半不可能区域，并用left<=right作为继续查找的门槛。学生能比较两类查找的适用条件与代价，形成“无序用顺序、有序可二分、重复键需约定返回策略”的选择意识。课堂结束时，学生不只提交两份代码，还要提交一张边界测试表和一段不超过八十字的算法选择说明，体现从会写到会判断的生长。四、教学重点与难点重点是查找过程的程序化表达：目标值、序列、索引、比较、返回五个要素缺一不可；顺序查找中“找到立即return”与“遍历结束返回1”的分工必须清晰；二分查找中区间收缩必须闭合并可见。难点是二分查找的边界一致性，特别是right=mid1与left=mid+1为什么不能写成right=mid或left=mid。突破办法不是强调死记，而是让学生在长度为5、6的小序列上手工画出left、right、mid的变化，观察死循环从何而来。五、教学策略与资源采用情境驱动、对比建构、错误诊所、变量追踪、当堂评测五种策略。环境为机房Python3.x，配发任务单、测试数据表、半成品代码与计时小工具。黑板采用左右双栏：左栏保留顺序查找的通用逻辑，右栏生成二分查找的区间收缩图。投影只展示关键代码和学生样本，不堆砌概念。评价量规前置，学生开始编码前就知道教师将从正确性、边界、效率说明、代码可读性四个维度观课。六、教学过程环节一：问题入场，激活生活查找上课开始，屏幕呈现一张模拟图书借阅清单：学号、姓名、借阅册数、是否逾期。教师提出任务：给定学号20240317，判断该生是否在清单中，若在，输出所在行号。学生凭直觉会说“一行一行看”。教师不否定，顺势要求把这句话改写成机器能执行的指令：从哪里开始，每次看什么，什么时候停，停了以后报告什么。三分钟独立书写，两名学生口述，教师只记录动词：取、比、等、停、返。随后教师给出两个相反追问：如果清单一万行，逐行看仍然可行吗；如果清单已按学号升序排列，还要从第一行开始吗。学生意见分化，课堂认知冲突形成。此时板书本节核心问题：查找不是“看一眼”，而是“在规则约束下减少不确定”。该导语简短，却把顺序与二分两条路线同时放到学生面前。环节二：顺序查找，把遍历写成可靠代码教师给出最小数据样例a=[12,7,19,7,25]，目标key=19。学生先用手指数索引，口答比较序列：12不是，7不是，19是，返回索引2。教师强调返回值是位置而非元素本身，因为位置能继续支持修改、删除、统计，元素值却不能唯一标识重复数据。学生独立完成基础版本。约定函数头为defseq_search(a,key):，找到返回下标，未找到返回1。教师巡视，收集三类典型写法：使用foriinrange(len(a))；使用forxina但丢失下标；使用while但忘记i+=1。展示时不点名，只让全班判断哪一版最能表达“位置意识”。基准代码共同沉淀为：defseq_search(a,key):换行进入函数体；foriinrange(len(a)):；ifa[i]==key:；returni；循环自然结束后再return1。教师用红笔标出两个return的层级：前者在循环体内，命中即离场；后者与for对齐，表示全部比较失败后的统一交代。学生闭眼复述这条结构，再睁眼修改自己代码。测试环节要求用四组数据：key在首位、在末位、在中间、不存在。学生填写实际比较次数，观察“最好1次、最坏n次、平均约n/2次”的经验规律。教师不急着给复杂度名词，只让学生写下结论：顺序查找不挑数据顺序，代价是可能一直走到尽头。环节三：错误诊所，让bug说话屏幕投放三份带病代码。第一份把return1缩进进for，导致只检查第一个元素就匆忙失败；第二份在找到后置flag=True却继续循环，重复元素场景中返回意义混乱；第三份函数没有返回值，打印了结果却无法被其他程序复用。学生分组认领病灶，要求用一句因果句说明“因为什么，所以错”，并给出修复行。这个环节的关键是把错误从羞耻转成证据。教师引导学生认识到，查找函数的价值在于可被调用，调用者需要稳定约定：整数下标表示成功，1表示失败。打印只是人机对话，返回才是程序协作。课堂语言由此从“对不对”升级为“接口清不清”。环节四：有序序列引出二分查找教师换成升序列表b=[3,8,15,24,36,47,59]，目标24。提问：既然已经排好序，是否有办法不必从头看。学生会提出看中间。教师追问：看到15比24小，说明什么；看到36比24大，又说明什么。学生逐步说出“目标只可能在右半段”或“左半段不可能”。教师把这句话形式化为区间概念：当前可能区域用left与right夹住，初始left=0，right=len(b)1。黑板画出第一轮：left=0，right=6，mid=3，b[mid]=24，正好命中。再换key=8重画：left=0，right=6，mid=3，24比8大，右边界左移到mid1，即right=2；新区间left=0，right=2，mid=1，命中。学生亲眼看到可能区域从7个缩到3个，再缩到1个，效率不是口号，而是区间长度在每轮后变小。教师给出可视化关系：mid=(left+right)//2；若a[mid]<key，则left=mid+1；若a[mid]>key，则right=mid1；若相等，返回mid。每一条更新都与“mid已经检查过，不应再留在候选区”对应，防止边界回吞。环节五：二分查找实现与边界攻坚学生先写伪码，再转为函数defbin_search(a,key):。教师要求显式写出whileleft<=right:，并解释等号的含义：当left与right重合时，区间还剩一个元素，放弃比较会漏解；只有当left>right，候选区才真正为空。这个门槛句被写入任务单显眼位置。代码形成过程中，教师设置“停顿点”：每名学生运行前必须预测某组输入的三轮left、right、mid。预测与程序输出不一致者，不许直接改代码，要先在纸上标出分歧。此举针对学生“改到能跑”的冲动，把调试拉回推演。基准实现整理为：defbin_search(a,key):；left=0；right=len(a)1；whileleft<=right:；mid=(left+right)//2；ifa[mid]==key:returnmid；elifa[mid]<key:left=mid+1；else:right=mid1；循环外return1。教师提醒：本版返回任一命中下标，若存在重复键且需返回首次出现，应另行约定，不在本课展开，但要知道需求会变。难点突破用反例完成。取a=[1,3,5]，key=4，若误写right=mid，第一轮mid=1，a[mid]=3<4，left=2；第二轮mid=2，a[mid]=5>4，若right=mid则right仍为2，left=2，区间不再缩小，进入死循环。学生观察变量表后自己总结：已检查位置必须从候选区剔除。这个从错误中长出的规则，比直接背诵更牢。环节六：对照实验，用数据选择算法全班进入计时任务。教师提供三个数据集：无序小表、有序大表、含重复键的有序表。学生分别运行顺序查找与二分查找，记录可不可用、大约比较次数、结果是否符合预期。由于机房计时受环境影响，评价不迷信毫秒，而比较“趋势”：n增大时，顺序查找的最坏情况随长度同步变长；二分查找在有序条件下增长极缓。讨论落点在条件而非名次。学生完成一句判断：当数据无序且规模不大，顺序查找诚实可靠；当数据有序且会被频繁查询，先排序再二分更划算；当只查一次且排序成本高，盲目排序并不精明。教师补充工程视角：算法选择离不开后续操作频率、数据更新频率、稳定性要求和内存约束，本课先建立“前提—收益”的最小模型。环节七：变式任务，分层达标基础层完成两个函数并通过八组断言：seq_search([4,2,9],2)返回1；seq_search([4,2,9],8)返回1；bin_search([1,3,5,7],7)返回3；bin_search([1,3,5,7],2)返回1。要求断言打印True或False，不允许只看肉眼看输出。提高层改写顺序查找，使其返回所有命中下标组成的列表，空列表表示未找到。学生要处理“不能提前return”的变化，体验同一任务下接口改变引发结构改变。拓展层研究“查找第一个不小于key的位置”，在有序数组中用二分思想返回插入点，为后续bisect思想埋点，但不引入库函数替代表达。对暂未完成二分的学生，教师提供“骨架卡”：只保留while、三个分支和return，让学生填边界更新；对已完成学生抛出追问：若right初始写成len(a)，循环条件应如何改，为什么容易越界。不同路径在同一核心处汇合：区间定义必须与更新规则一致。环节八：课堂小结，沉淀可迁移句式学生用三句话收束。第一句写顺序查找：从0号到n1号逐个比较，命中即返，穷尽失败。第二句写二分查找：有序前提下守住left、right，mid命中或排除半边，left越过right才宣告失败。第三句写选择：看数据是否有序、看查询频率、看返回位置约定。教师将三句话压缩成板书中的算法名片，要求课后能默写结构而非照抄代码。本环节不追求热闹回顾，而要求学生把“我运行成功了”改述为“我知道它在哪里可能失败”。能说出失败条件，才算真正拥有算法。七、板书设计左栏标题为顺序查找。要点如下：输入a、key；过程i从0到n1；a[i]==key则returni；循环结束return1；特点是不需有序、最坏n次比较。旁侧画一条直线箭头，表示候选区一次只排除一个位置。右栏标题为二分查找。要点如下：前提a有序；left=0，right=len(a)1；mid=(left+right)//2；a[mid]<key则left=mid+1；a[mid]>key则right=mid1；left>right时return1。旁侧画区间被反复切半的阶梯，标注“每轮扔掉已查mid与不可能半边”。中间留白写课堂警句：返回值是接口，边界是承诺，有序是二分的入场券。三句话分别指向工程协作、程序正确性、算法适用条件。八、作业设计必做一：完善课堂两个函数，配套六组以上assert，覆盖首尾、中间、不存在、空列表、单元素列表。提交时附一张手写或电子变量追踪表，任选一组二分查找展示三轮内left、right、mid的变化。必做二：阅读一段真实场景描述，校园失物招领系统按物品编号升序存储，每天有大量查询也有新登记。回答采用什么查找策略，是否需要先排序，新增物品如何影响有序性。答案限定一百五十字，重点看是否把算法选择与业务频率相连。选做：在保持主逻辑不变前提下，为二分查找增加比较次数计数器，对长度从10到10000的有序列表抽样测试，画出比较次数随规模变化的趋势草图。允许手工采样，不强制精确统计，目标是感受“增长很慢”的形状。九、课堂评价量规正确性维度：存在与不存在均能返回约定结果，重复键下说明返回策略，空列表不崩溃。边界维度：循环条件与区间更新一致，能解释为何排除mid。效率维度：能定性说明顺序查找线性扫描、二分查找逐轮减半，并知道二