使用二进制搜索猜测浮点值
Guessing a float value using binary search
我想编写一个程序来猜测一个人选择的数字，方法是向这个人提问“你的数字是否大于 x？”。
如果数字是有限大小的整数（比如 32 位），那么使用二分查找很容易猜到 - 32 个问题就足够了。
现在，假设此人选择一个由浮点变量表示的实数（例如 C++ 中的 float，它也使用 32 位）。 float 有有限多个可能的值，因此我的程序应该仍然能够使用少量问题猜出该人选择的确切浮点数。但是，我不确定如何使用二进制搜索来做到这一点，因为 float 的可能值不是均匀分布的。
问题：如何使用“你的数字是否大于 x”形式的少量问题来猜测 float 值？
为了使问题更具体，假设给你一个函数bool is_greater_than(float x)。您需要调用多少次此函数才能猜出数字？只调用32次就能搞定吗？
检查符号后，您必须尽快找到指数。对于 32 位浮点数，有 255 个可能的指数值（第 256 个为特殊数字保留）。所以在第一阶段对指数值进行二进制搜索。最多8步（8位指数）
然后执行通常的二进制搜索，步长减半以确定尾数的确切值 - 最多 23 步（尾数的 23 位）
这种方法可以克服 not evenly spaced 问题，但还有另一个问题 - 用户可以（并且几乎肯定会）猜测没有精确二进制表示的数字，因此您必须使用一些 epsylon 容差（取决于指数)
我想编写一个程序来猜测一个人选择的数字，方法是向这个人提问“你的数字是否大于 x？”。
如果数字是有限大小的整数（比如 32 位），那么使用二分查找很容易猜到 - 32 个问题就足够了。
现在，假设此人选择一个由浮点变量表示的实数（例如 C++ 中的 float，它也使用 32 位）。 float 有有限多个可能的值，因此我的程序应该仍然能够使用少量问题猜出该人选择的确切浮点数。但是，我不确定如何使用二进制搜索来做到这一点，因为 float 的可能值不是均匀分布的。
问题：如何使用“你的数字是否大于 x”形式的少量问题来猜测 float 值？
为了使问题更具体，假设给你一个函数bool is_greater_than(float x)。您需要调用多少次此函数才能猜出数字？只调用32次就能搞定吗？
检查符号后，您必须尽快找到指数。对于 32 位浮点数，有 255 个可能的指数值（第 256 个为特殊数字保留）。所以在第一阶段对指数值进行二进制搜索。最多8步（8位指数）
然后执行通常的二进制搜索，步长减半以确定尾数的确切值 - 最多 23 步（尾数的 23 位）
这种方法可以克服 not evenly spaced 问题，但还有另一个问题 - 用户可以（并且几乎肯定会）猜测没有精确二进制表示的数字，因此您必须使用一些 epsylon 容差（取决于指数)