( ! ) Notice: Undefined index: mobile in /var/www/html/head.php on line 16
Call Stack
#TimeMemoryFunctionLocation
10.0001230624{main}( ).../view.php:0
20.0001231368include( '/var/www/html/head.php' ).../view.php:2
30.0010250728isMobile( ).../head.php:30
数学思维训练网 - 小学计算思维课程(16)-二分搜索

小学计算思维课程(16)-二分搜索

小学计算思维课程(16)-二分搜索

本书共26课,如果您有好的建议,请联系作者:浙江省新昌县城西小学 唐明 147885198@qq.com


第十六课:二分搜索

上节课我们学习了线性搜索算法,虽然它非常简单,但是它有一个致使的缺陷——速度太慢!如果数据太多,我们将会把时间都浪费在等待计算机找到数据上。所以计算机科学家发明了很多快速的搜索算法,二分搜索是其中一种高效和通用的算法,它和第15课学的猜1-100之间数字的方法很类似。

准备:还是使用25张卡片,但不要让搭档看到这些卡片,随机选一张卡片作为你的秘密战舰,并告诉你的搭档。然后将这些卡片从小到大按顺序排好,并让背面朝上。

活动:用最小的翻牌次数找到秘密战舰。

问题:

1.你一共用了几次猜中对手的秘密战舰?和上节课的成绩相比有进步吗?是什么原因让你进步了?

2.同学中,最快用了几次猜中秘密战舰,最差的又是几次呢?

3.你是怎样用二分查找的办法来搜索秘密战舰的?

4.如果秘密战舰不在队列中会发生什么情况?要猜多少次才能发现?

5.如果有100张卡片,要猜多少次才一定能赢得游戏?

从上面的游戏中我们发现,二分搜索法的翻牌次数远比线性搜索少,因为它只要检查队列的中间就可以锁定秘密战舰位于哪一半,这样一来,每猜一次就相当于将待查找的目标数量减少了一半。现回头看上节课超市里10000件商品的搜索,使用二分搜索法,仅需要14次比较,就可以找到目标商品,快到让人无法察觉。

想一想,采用二分搜索法,在1000000个商品中搜索一件商品需要多少次才能找到目标?(提示:可以将1000000除以2,再除以2,依次类推,一共需要除多少次能得到1呢?)