performance - 数字猜谜游戏

Question

通常，给定一些秘密数字的数字猜谜游戏算法只是对二分搜索算法的修改，如果知道猜测是大于还是小于秘密数字。假设秘密数字是 13。算法会尝试 1（小于 13）、2（小于 13）、4（小于 13）、8（小于 13）、16（大于 13，回溯）、10（小于 13), 13(等于秘密，停止。)

但是，如果不知道猜测是小于还是大于秘密数字，并且唯一的状态是相等或不相等怎么办？什么算法最有效？当然不是暴力破解...

编辑：对于这两种情况，数字可能有一个上限和下限。

Answer 1

我不确定您对此类问题所期望的性能提升。正如大多数人所建议的那样，没有重要的方法可以改善 O(n) 的最坏情况。您还可以坚持使用二分搜索方法，其中每个不相等的猜测最初都被视为小于操作“<”，一旦此列表用尽，您可以将每个不相等的猜测视为大于操作 >。在玩“猜数字游戏”的实际场景中，我相信这“可能”比顺序暴力更好。

一般来说，如果我们能找到一种算法来准确地猜测最小猜测中的数字，我相信世界各地的许多游戏很快就会变得多余:)

Answer 2

好吧，您所拥有的信息是答案不正确。由于它是唯一可用的信息，我认为蛮力将是唯一的方法。你也可以从零开始然后上升。

Answer 3

如果你想象一个对手直到他们不得不决定这个数字时才真正决定这个数字，那么你可以看到你可能不得不依次询问每个数字。他们可以简单地说“错误答案”，直到您猜出所有可能的数字，并且他们的答案可能是真实的，基于您猜到的最后一个数字的初始选择。

Answer 4

如果相等/不相等是您获得的唯一信息，那么没有任何算法可以比蛮力（即从下限开始到上限）为您提供更好的平均情况或更好的最坏情况性能。

为了获得更好的平均案例性能，您需要一些额外的信息。至少有一些统计数据，比如“只有 10% 的秘密数字低于 20”等，然后可以用来获得更好的平均案例性能（在这个例子中，可能是从 21 开始搜索）。

即便如此，最坏情况下的性能仍然不会比蛮力好。