这节课我们来学习二分查找，教大家用二分查找的方法在Scratch中同样来实现程序：查找某个数是否属于斐波那契数列中，若属于，要求说出查找次数和所在的位置；最后对比二分查找和顺序查找。

二分查找定义：

在一个已知有序数列中找出与给定关键字相同的数。

算法流程：

1、给定一个有序数组a，和一个要查找的关键字s；

2、将a的中间项与s进行比较，如果s等于a的中间项，则查找成功；如果s比a的中间项要小，则到a的前半部分继续查找，反之，则到a的后半部分继续查找；

3、 如此反复，直到在a中找到s，或者没有元素可以继续找。

第一步， 生成斐波那契数列和要查找的数字

斐波那契数列的生成与上节课顺序查找中的相同。

第二步，构造二分查找函数并调用

1、建立变量searchnumber，left，right，count并初始化；searchnumber用来保存输入的要查找的数；left和right分别用来定位当前数列的最左边数和最右边数的位置；count用于计算并保存查找次数；

2、建立循环直到数列全部遍历完（即Left>Right）；

每循环一次，count增加1，获取当前数列中间项，并用变量middle保存；

将当前中间项（即数列的第middle项）与searchnumber进行比较，如果相等，则查找成功，并说出查找次数和所处位置；

如果当前中间项比searchnumber要小，则到当前数列的后半部分继续查找，反之，则到当前数列的前半部分继续查找；

3、如果全部遍历完斐波那契数列后，还没有查找到输入的数字，则查找失败！

4、调用顺序查找函数：将

写入到生成斐波那契数列的代码后面。

完整代码是：