这是 Steve Balmer 说他问的一个 面试问题 - 我想到了 1 到 100 之间的一个整数。你猜对了。如果你没答对，我会告诉你你是高还是低。您希望尽量减少预期中的猜测次数。
如果巴尔默想到的数字统一从 1 到 100 抽取，二分查找将给出我们期望的最少猜测数。
但是，如果巴尔默不是均匀地绘制整数，而是根据概率分布绘制整数，该怎么办？概率分布表示为数组 p，其中 p[j] 是选择数字 j 的概率。我们应该选择什么策略来猜测他以预期猜测次数最少的方式选出的数字？
我的尝试：如果 p[j] 在整数上是均匀的，那么策略应该变成二分搜索。所以，我的想法是，我们猜测不排除的数字中的数字j，使其左右的概率之和尽可能平衡。我们不断根据这个标准进行猜测，直到猜出数字为止。我推测这是最佳策略，但不知道从哪里开始尝试证明这一点。
或者可能不存在适用于所有数组 p 的“一致最优”策略，它取决于特定的数组。那会令人失望。
这个问题映射到最优二叉搜索树，因为每个策略都可以表示为二叉树。这可以通过 Cormen 等人的算法简介一书的 15.5 节中介绍的动态规划来解决。第三版。