少儿趣味编程Scratch算法挑战《二分查找法》（教案+源文件）

算法挑战：二分查找法 ( 今日任务： ) 今日我们来利用 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<list （ 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<list （ 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 n<list(mid) Y ) 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） 试着总结一下二分法的优缺点？ 优点是比较次数少，查找速度