-2 puzzle algorithm math binary-search
如果我要求一个人在他的脑海中选择1到1200之间的数字.如果我只能提出他只会回答"是"或"否"的问题,那么在我得到他在脑海中选择的号码的答案之前,我需要问多少个问题？
我正在寻找尽可能少的问题.任何经过验证的解决方案都是可观的
要确定选择1和n之间的数字,您需要至少提出log 2 n个问题.没有可能做得更好的方法.
这个答案的直觉如下.假设你总共提出了k个问题.即使这些问题彼此依赖,您可以收到的不同可能答案的最大数量为2 k.由于可以选择n个可能的数字,因此您需要选择k
2 ķ ≥Ñ
这恰恰发生在何时
ķ≥日志2 Ñ
换句话说,你必须要求至少log 2 n个问题才能够有足够的不同可能结果来将每个可能的数字与一些可能的结果联系起来.由于问题的数量必须是自然数,问题的最小数量可以问必须至少⌈log 2 n⌉
这纯粹是答案的下限.在这一点上,我们不能排除你可能需要更多问题才能得到答案的可能性.然而,事实是,我们知道的二进制搜索算法意味着,我们知道,你永远需要比⌈log多2个 n⌉问题,得到的答案,因为这是你会问,如果你正在做一个二进制的问题的数量搜索.这意味着二进制搜索算法必须是最优的,因为没有可能的方式来询问较少数量的问题.
希望这可以帮助!