从零开始学算法:基于Python
上QQ阅读APP看本书,新人免费读10天
设备和账号都新为新人

1.1.1 好玩的猜数游戏

我们小时候应该都玩过这样一个游戏:假设你和小王玩这个游戏,你在一张纸上写上0~100的某个数字,且不能让小王看见,小王在不知道纸上数字的情况下需要猜中这个纸上的数字。在小王说完一个数字以后,你需要提示小王其猜测的数字是大于纸上数字,还是小于纸上数字,小王要用最少的次数猜中这个数字。你看了看小王,在纸上轻轻地写下了66,开始让小王猜。

小王:“50。”

你:“小了。”

小王:“75。”

你:“大了。”

小王:“62。”

你:“小了。”

小王:“68。”

你:“大了。”

小王:“65。”

你:“小了。”

小王:“66。”

你:“猜中啦!”

小王只用了6次就猜中了写在纸片上的数字,其实无论纸上写什么数字,只要我们了解了二分搜索技术,就可以保证在7次之内猜中数字。那么猜数游戏中到底隐藏着什么样的秘密呢?