4.3.1 非数值计算:二分查找法课件-2025-2026学年教科版高中信息技术必修一

该高中信息技术课件聚焦二分查找法，通过“猜数字游戏”情境导入，从生活问题出发，逐步过渡到算法原理（方法、核心逻辑、分割步骤），结合实例分析（如查找22、20的过程）和课堂练习，搭建从具体到抽象的学习支架。 其亮点在于情境化教学与分步解析结合，以猜数字游戏激发兴趣，通过实例（如数组查找22的三次分割）培养计算思维，课堂小练（如判断有序数列、分析left/right变化）提升信息意识。帮助学生理解算法逻辑，教师可高效开展教学。

4.3 非数值计算 —— 二分查找法 猜 数 字 游 戏 给定一个1-100范围内的数，猜数字，与给定的数字进行比较，给出提示（大了还是小了？）并记录猜的次数。 怎样才能最快的找到正确答案？ 第一次猜50—>小了—>范围变成51-100 第二次猜75—>小了—>范围变成76-100 每次猜中间的数，这样每次能缩小一半的范围。 50 小了 大了 75 25 87 62 37 13 …… …… …… 小了 大了 小了 大了 …… 2 一 二分查找法 二分查找又叫折半查找，将数列有序排列，采用跳跃式的方式查找数据。 方法：以递增数列为例，以中点位置元素作为比较对象，若要查找元素值小于该中点元素，将待查找序列缩小为左半部分，否则为右半部分。如此每次比较后都能将查找区间缩小一半。 第一次分割 第二次分割 第三次分割 3 一 二分查找法 左边界left 右边界right 目标数key 中间 mid=(left+right)//2 若mid对应的值>key，则查找范围变为左半区间，右边界更新为right=mid-1, left不变。 左边界 left 右边界 right 目标数key 中间 mid= (left+right)//2 若mid对应的值<key，则查找范围变为右半区间，左边界更新为left=mid+1, right不变。 “//”向下取整，舍弃小数部分 比如(2+3)//2=2 left、right和mid指向的都是数据的下标值 4 一 二分查找法 目标数：22 5 9 12 18 22 31 35 共7个数 下标： 1 2 3 4 5 6 7 第一次：mid=4，下标4对应的值为18，18<22，所以舍弃左半部分，left=mid+1=5，right不变仍为7 left=1 right=7 mid=(1+7)//2=4 5 9 12 18 22 31 35 下标： 1 2 3 4 5 6 7 left=5 right=7 mid= (5+7)//2=6 第二次：left=5，mid=(5+7)//2=6，31>22，舍弃右半部分，right=mid-1=5 22 31 35 下标： 5 6 7 mid= (5+5)//2=5 right left 第三次：这时mid=(5+5)//2=5，对应的值为22，找到目标值22 5 一 二分查找法 目标数：20 55 下标：1 2 3 4 5 6 7 8 9 10 left=1 right=10 left=1 right=mid-1=4 left=mid+1=3 right=4 第一轮： 第二轮： 第三轮： 5 16 20 27 30 36 44 55 60 67 left mid=(1+10)//2=5 right 5 16 20 27 30>20，舍弃右半部分 下标： 1 2 3 4 left mid=(1+4)//2=2 right 16<20，舍弃左半部分 20 27 下标： 3 4 left mid=(3+4)//2=3 right 20=20，找到目标数 最坏的情况需要查找n次满足：2n>N(N为查找的总数量），n=⌊log2N ⌋+1 6 课 堂 小 练 练习1 1、二分查找又称折半查找，是一种应用于有序数列的高效查找算法。下列数列中适合二分查找算法的是( ) A.85 78 59 53 19 18 B.67 62 68 41 1 7 C.11 99 4 25 3 39 D.43 71 78 81 6 55 A 7 课 堂 小 练 练习2 2、在一个有序数列 4, 9, 15, 22, 28, 33, 40（共7个数据）中，用二分查找法查找目标值 28。第一次比较结束后，left 和 right 的值分别是多少？（ ） A. left=1, right=3 B. left=5, right=7 C. left=1, right=7 D. left=4, right=7 B 解析： 初始：left = 1，right = 7 第1次比较：mid=(1+7)//2=4，位置4对应的值是 22，22 <28，目标在右半段， 所以 left = mid +1 = 5，right 不变，仍为 7 第一次比较结束后：left = 5，right = 7 下标：1 2 3 4 5 6 7 8 $