2024年4月30日发(作者：)

原创学案 个人

第五十二课 二分法

今日任务：

今日我们来利用scratch进行一次二分查找算法的探究。所谓二分查找法，就是这样一

种查找思路，但是，它的使用有一定的局限性，被查找的数列必须是有序数列。它的原理其

实很简单，可以这样描述：将

所查找的数字和有序数列中间的数字进行比较，如果所查找数字大

于有序数列的中间位置数字，那么就在有序数列的后半部分继续进行折半查找，如果所查找数字小于

有序数列的中间位置数字，那么就在有序数列的前半部分继续进行折半查找，以此往复，直到找到所

查找数字或者找完链表发现所查找数字不在数列中为止。

我们简单用图形来解释一下这个二分法是如何运行的：

有这样一个有序序列，数列中数字全部按照升序排列：

我们要在该数列中查找数字11，我们来看看程序是怎样运行的！

Left=1

Mid=11 Right=20

1,3,5,7,11,33,37,42,56,79,88,102,113,117,128,142,155,161,177,208

Mid=（left+right）/2 四舍五入取整

11≠list（11）且11

找！

Left=1 Mid=6 Right=10

1,3,5,7,11,33,37,42,56,79,88,102,113,117,128,142,155,161,177,208

11≠list（6）且11

Left=1 Right=5

1,3,5,7,11,33,37,42,56,79,88,102,113,117,128,142,155,161,177,208

Mid=3

11≠list（3）且11>list（3）,继续在前后半部分查

找！

原创学案 个人

原创学案 个人

Left=4 Right=5

1,3,5,7,11,33,37,42,56,79,88,102,113,117,128,142,155,161,177,208

Mid=5

11=list（5），查找结束！返回列表位置5.

如果是按照顺序查找法，需要查找5次，而用二分法只需要4次就可以查找到了，如果有序数列更复

杂一些更长一些，二分法比顺序查找法的优势就更加明显！

本课重难点：

（1）了解二分查找的方法；

（2）能够通过scratch编程实现二分查找法；

任务解读flow chart：

开 始

键盘输入n

没有找到n

N

Right≥left

Y

Mid=（right+left）/2 四舍五入取整

Y

n=list(mid)

N

n

Y

right=mid-1

N

left=mid+1

找到了，输出mid值

结 束

原创学案 个人

原创学案 个人

跟我来挑战Follow me：

第一步：启动scratch软件；

第二步：点击上方的“文件”→“保存”→保存到桌面，文件名：二分查找 →点击“保存”；

（第二步很很很重要，我希望所有的学生都能养成及时保存作品的好习惯！）

第三步：首先我们先生成一个斐波那契数列

键盘输入n

程序较长，我们单独将二分法算法程序

定义为一个单独地功能块（子程序），

用的时候调用就可以了！

原创学案 个人

原创学案 个人

还记得left和right、mid分别是什么？再提醒一下！

Right≥left

Mid=（right+left）/2 四舍五入取整

Count是我用来记录查找次数

的变量

找到了，输出mid值

n=list(mid)

原创学案 个人

原创学案 个人

没有找到n

最后直接调用这个功能块即可：

该程序的运行结果是：

课后思考：

（1） 试着总结一下二分法的优缺点？

优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，

且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。

（2）想一想，二分查找法的用途有哪些？二分查找法是最省优查找算法吗？有没有更高

效的算法处理有序数列？

（3）自己尝试设计出一个随即有序数列，尝试用二分法去查找结果。

原创学案 个人