※ 引述《Rushia (みけねこ的鼻屎)》之铭言:
: 374. Guess Number Higher or Lower
: 龙大想要和边板仔玩猜数字游戏,只有龙大知道答案的数字是什么,当我们猜的时候龙
: 大会根据你猜的数字给你一个数字:
: 龙大提供一个函数guess(int num)返回一个整数
: -1:你猜的数字太小了
: 1:你猜的数字太大了
: 0:你觉得是这个数字那就是吧- -
: 我们返回龙大才知道的数字。
今天的题目虽然是 easy
而且小时候有玩过猜数字的话应该是秒解
不过这是 binary search 蛮有趣的一个例子
因为这是一个并非在已排序阵列中找值的例子
(当然你可以说我们是在
[1, 1, ..., 1, 0, -1, -1, ..., -1]
中找 0 的位置,只是这个阵列可以非常大: 2^32 - 1
而且只能用 guess() 来获得阵列的值)
但我要觉得这反而才比较接近 binary search 的本来样貌
以前看过一些蛮有趣的文章,可以看一看 general 版本的 binary search
https://scm.iis.sinica.edu.tw/ncs/2010/03/binary-search-revisited/
https://scm.iis.sinica.edu.tw/ncs/2010/03/binary-search-revisited-02/