指数的威力与二分查找法

首先,还是问个问题。
假设现在有张1mm厚的纸,非常柔软,可以对折无数次,每对折一次,厚度便翻一番。
已知地球距月球39万公里,请问对折多少次后,厚度会超过地球到月球的距离?

我们先凭感觉估计一下,我觉得需要1万次,你觉得多少次合适呢?

下面我们来算一下,

对折次数 厚度
1 2mm
2 4mm


3 8mm
4 16mm
5 32mm
6 64mm
7 128mm
8 256mm
9 512mm
10 1024mm
———单位换为米———-
11 2.048m
12 4.056m
13 8.192m
14 16.384m
15 32.768m
16 65.536m
17 131.072m
18 262.144m
19 524.288m
20 1048.576m
————已经到千米了哦—————
21 2.097152km
22 4.194304km
23 8.388608km
24 16.777216km
25 33.554432km
26 67.108864km
27 134.217728km
28 268.435456km
29 536.870912km
30 1073.741824km
—————–已经超过1000km了———————-
31 2147.483648km
32 4294.967296km
33 8589.934592km
34 17179.869184km
35 34359.738368km
36 68719.476736km
37 137438.953472km
38 274877.906944km
39 549755.813888km

对折39次达到了549755.813888km,已经超过了地球和月球的距离了。

怎么样?是不是觉得很恐怖?我第一次看到的时候觉得好神奇。
仅仅是反复对折,数字不断翻倍,很快就得出了非常庞大的数字。我们把这种数字急速增长的情况称为“指数爆炸”。

那我们反过来来思考,是不就是成为了我们的二分查找法呢?

寻找犯人的思考题
假设有15个犯罪嫌疑人排成一排,其中只有一个是真正的罪犯,你要通过问他们“罪犯在哪里?”来找出真正的罪犯,而罪犯会回答你三种答案
1、我是罪犯
2、罪犯在我左边
3、罪犯在我右边

问,仅通过3次问话找出真正的罪犯,应该怎样问话?

可能15人有点多,那我们缩小一下问题范围,假设犯人在3人中。
这中情况下,我们只要向中间的提问,就能立刻确定谁是犯人。
得到回答情况:
1、我是犯人 被提问者是犯人
2、罪犯在我左边 被提问者左边的人是犯人
3、罪犯在我右边 被提问者右边的人是犯人

按照这个思路,我们是否能通过三次问话在15人中找出犯人呢?我们来试一试。

第一次,向正中间的人提问,如果被提问者本人是犯人,那么提问结束。
第二次,向筛选出的7人里的最中间那个人提问,如果被提问者本人是犯人,那么提问结束。
最后一次,先筛选出的3个人里面正中间的那个人提问,找出真正的犯人。

怎么样?明白了么?我们可以把犯人从左到右以此编号1-15,然后通过返回值等于(被提问者是犯人)、大于(犯人在被提问者右边)、小于(犯人在被提问者左边)来快速找到我们要找的数字。

15个数不算多,可是联想上我们刚才的指数爆炸呢?判断3次我们可以在15个数据中找到目标数据,判断10次,就可以在2047个数据中找到目标数据,20次就能在209万7151个条数据中找到目标数据,30次就能在21亿4748万3648条数据中找到目标数据……

二分查找的关键在于,每判断一次就能删选出近一半的数据,因此,必须将查找对象有序排列,否则我们就无法判断目标数据是在左边还是在右边了。
二分查找每多判断1次就能从近2倍的数据中找出目标数据,非常有效的利用了指数爆炸,大家明白了么?

发表评论

电子邮件地址不会被公开。 必填项已用*标注

您可以使用这些HTML标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

You must enable javascript to see captcha here!