查找算法——二分查找

难度:

尊敬的用户,该视频为旧版会员课程,仅限已购买的会员查看

编玩边学最新推出哈克尼斯圆桌课堂模式

更优质的课程与服务,系统的课程体系,提供国内最专业的儿童编程教育

查看新版课程

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

二分查找定义

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

算法流程:

1. 给定一个有序数组a,和一个要查找的关键字s
           2.a的中间项与s进行比较,如果s等于a的中间项,则查找成功;如果sa的中间项要小,则到a的前半部分继续查找,反之,则到a的后半部分继续查找;

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

 

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

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

1.png

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

2.1)建立变量searchnumberleftrightcount并初始化;searchnumber用来保存输入的要查找的数;leftright分别用来定位当前数列的最左边数和最右边数的位置;count用于计算并保存查找次数;

 

2.png

2.2)建立循环直到数列全部遍历完(即Left>Right);

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

3.png

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

4.png

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

5.png

2.3)如果全部遍历完斐波那契数列后,还没有查找到输入的数字,则查找失败!

2.4)调用顺序查找函数:将 6.png写入到生成斐波那契数列的代码后面。

 

完整代码是

          

7.png

8.png

 

举一反三

跟顺序查找一样,通过利用二分查找算法,同样可以实现

  • 电话簿里查找电话号码

  • 在学校学生记录中查找某学号寻找对应同学信息

  • 火车站检票时查找身份证号码以验证某人是否是犯罪分子.

 

思考

       请大家思考,从原理、适用条件、查找次数等家角度对二分查找和顺序查找进行对比.


作业: 


给定一个数列 { 1, 2, 3, 3, 5, 7, 9, 9, 9, 9, 14, 18} ,在该数列中用二分查找的方法查找是否存在SS = 9)?若存在,请给出S的个数及其对应的位置。(注意:要给出所有的SS=9))




 登录/注册后发表或回复问题

在本系列的课程中,我们将经典算法在scratch中实现,你准备好了吗?挑战你自己的时刻到了

通过本系列课程的学习,你将会学到编程的精髓——算法,成为编程专家


###讲课老师:王代银,北大2015级硕士,算法、黑客技术高手,将艰深晦涩的算法问题用scratch讲得有趣易懂,这套scratch算法课程备受众多中小学信息技术课教师推崇,被大量用作参考教材!