资源简介

算法挑战：二分查找法
(
今日任务：
)
今日我们来利用 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（
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（
6
）
,
继续在前半部分查找！
)
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
）
,
继续在
前后半部分查
)
(
Mid=5
) (
没有找到
n
) (
N
) (
Mid=
（
right+left
）
/2
四舍五
入取整
) (
Y
) (
right=mid-1
) (
Right
≥
left
Y
n=list(mid)
left=mid+1
N
N
nY
)
Left=4
Right=5
1,3,5,7,11,33,37,42,56,79,88,102,113,117,128,142,155,161,177,208
(
11=list
（
5
），
查找结束！
返回列表位置
5.
)
如果是按照顺序查找法， 需要查找 5 次， 而用二分法只需要 4 次就可以查找到了， 如果有序数列更复 杂一些更长一些， 二分法比顺序查找法的优势就更加明显！
(
本课重难点：
)
（1）了解二分查找的方法；
（2）能够通过 scratch 编程实现二分查找法；
(
任务解读
flowchart
：
)
开 始
(
键盘输入
n
)
(
找到了，输出
mid
值
)
结 束
(
跟我来挑战
Follow
me
：
)
第一步：启动 scratch 软件；
第二步： 点击上方的“文件”→ “保存”→保存到桌面，文件名： 二分查找 →点击“保存”；
（第二步很很很重要，我希望所有的学生都能养成及时保存作品的好习惯！）
第三步： 首先我们先生成一个斐波那契数列
(
键盘输入
n
)
程序较长，我们单独将二分法算法程序 定义为一个单独地功能块（子程序）， 用的时候调用就可以了！
(
还记得
left
和
right
、
mid
分别是什么？再提醒一下！
)
(
Right
≥
left
)
Mid=（right+left）/2 四舍五入取整
Count 是我用来记录查找次数
的变量
(
找到了，输出
mid
值
)
n=list(mid)
没有找到 n
最后直接调用这个功能块即可：
该程序的运行结果是：
(
课后思考：
)
（1） 试着总结一下二分法的优缺点？
优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表， 且插入删除困难。因此， 折半查找方法适用于不经常变动而查找频繁的有序列表。
（2） 想一想， 二分查找法的用途有哪些？二分查找法是最省优查找算法吗？ 有没有更高 效的算法处理有序数列？
（3） 自己尝试设计出一个随即有序数列，尝试用二分法去查找结果。

展开更多......

收起↑