algorithm - float 的二进制搜索/二分法

Question

用二分查找很容易找到一个整数even if it can be arbitrarily large :先猜数量级，再继续划分区间。 This answer描述了如何找到任意有理数。

设置场景后，我的问题是相似的:我们如何猜测 IEEE 754 float ？假设它不是 NaN，但其他一切都是公平的游戏。对于每次猜测，您的程序都会被告知所讨论的数字是更高、相等还是更低。尽量减少最坏情况下所需的猜测次数。

(这不是家庭作业。不过，我可能会把它做成一个，如果结果是一个有趣的答案，而不仅仅是“通过大量的特殊情况处理来解决 float 问题”。 )

编辑:如果我更擅长搜索，我就能找到 answer ---但这只有在您已经知道重新解释为 int 有效时才有效(有某些警告)。所以留下这个。感谢 Harold 的出色回答!

Answer 1

IEEE-754 64 位 float 实际上是 64 位表示。此外，除了 NaN 值之外， float 比较和正值的整数比较之间没有区别。 (也就是说，两个未设置符号位的位模式将产生相同的比较结果，无论您将它们作为 int64_t 还是 double 进行比较，除非其中一个位模式是一个 float NaN-。)

这意味着你可以通过一次猜一位，在 64 次猜测中找到一个数字，即使这个数字是±∞。首先将数字与 0 进行比较；如果目标是“少”，则以与下面相同的方式产生猜测，但在猜测之前否定它们。 (由于 IEEE-754 float 是符号/大小，您可以通过将符号位设置为 1 来取反数字。或者您可以进行正位模式重新解释，然后 float 取反结果。)

之后，从最高位开始，一次猜测一位。如果数字大于或等于猜测，则将该位设置为 1；如果数字较小，则将该位设置为 0；并继续下一位，直到不再有为止。要构造猜测，请将位模式重新解释为 double。

有两个注意事项:

1. 您无法通过比较测试区分 ±0。这意味着如果你的对手想让你区分它们，他们将不得不为你提供一种询问与 -0 是否相等的方法，并且你必须在你显然确定数字为 0 之后使用该机制(这将在第 64 次猜测时发生)。这将增加一个猜测，总共 65 个。

2. 如果您确信目标不是 NaN，那么就没有其他问题。如果它可能是一个 NaN，你需要小心你如何比较:如果你总是问“X 小于这个猜测吗？”，事情会很好，因为 NaN 比较总是返回 false .这意味着在 11 个连续的“否”答案(不包括建立符号的那个)之后，您会发现自己在猜测 ∞，假设如果数字不小于 ∞，则它必须相等。但是，仅在这种情况下您还需要显式测试相等性，因为如果目标是 NaN，这也将是错误的。这不会将额外的猜测添加到计数中，因为它总是会在 64 次猜测用完之前很久发生。