二进制搜索以猜测实数 [英] Binary Search to guess real numbers

问题描述

考虑到一个相当普遍的问题-我正在考虑一个整数，因为我将用高，低或就是那个回答您的猜测，您能在O（log n）时间内猜到它吗！ -我遇到一个问题，这个问题略有变化，使我感到困惑：

Considering a fairly common problem - I am thinking of an integer, can you guess it in O(log n) time given that I will answer to your guesses in "high", "low" or "that's the one!" - I have come across a problem that is a slight variation that has me stumped:

我在想一个介于1和2之间的正实数N.将我的
数字猜到O（log log log N）时间的小数点后一位。

I am thinking of a positive real number between 1 and N. Guess my number to within one decimal place in O(log log log N) time.

我尝试解决通过尝试猜测10N而不是N来做到这一点，但这仍然不能为我提供O（log log log N）运行时。欢迎对此发表任何意见。

I tried solving this by trying to guess 10N instead of N but that would still not give me an O(log log log N) runtime. Any and all views on this are welcome.

谢谢

推荐答案

假设小数点后一位是指一个有效数字，在1到n之间有O（log（n））个可能的猜测。 1，2，3，...，10，20，30，...，100，200，300，...通过这些可能性进行二进制搜索将在O（log（log（log（n）））中产生正确的答案时间。为了便于编码，可以将其替换为对数量级进行二进制搜索，然后对第一位进行二进制搜索。但是，从信息理论上讲，不可能使用O（log（log（log（ n）））猜测以确定O（log（n））可能性之一。

Assuming "within one decimal place" means one significant figure, there are O(log(n)) possible guesses between 1 and n. 1, 2, 3, ..., 10, 20, 30, ..., 100, 200, 300, ... A binary search through these possibilities will produce the correct answer in O(log(log(n)) time. For ease of coding, this can be instead done as a binary search for the order of magnitude, followed by a binary search for the first digit. However, it is information-theoretically impossible to use O(log(log(log(n))) guesses to determine one of O(log(n)) possibilities.

示例：我正在考虑1到10000之间的数字。

Example: I'm thinking of a number between 1 and 10000.

是100吗？更高。
是1000？更低。
现在我们知道数量级了。

Is it 100? Higher. Is it 1000? Lower. Now we know the order of magnitude.

是500吗？更高。
是700吗？更高。
是800吗？更高。
是900。

Is it 500? Higher. Is it 700? Higher. Is it 800? Higher. It's 900.

这篇关于二进制搜索以猜测实数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！