无界的有大小提示的猜数游戏

KeyTo9_Fans

有界有大小提示的猜数游戏，结论和策略都很简单：

结论是最坏情况下要猜$(\lfloor\log_2(n)\rfloor+1)$次，$n$表示要猜的整数在$1$到$n$之间，

策略是二分法，先猜最中间，然后根据提示不断地猜剩余区间的最中间，直到猜对为止。

我现在遇到了一个无界的有大小提示的猜数游戏，只知道要猜的整数$x$最小是$1$，不知道最大是几。

我想在最坏情况下，猜对所需次数 减去 $(\lfloor\log_2(x)\rfloor+1)$ 的值要达到最小，$x$表示要猜的数。

我目前能想到的策略，猜对所需次数 减去 $(\lfloor\log_2(x)\rfloor+1)$ 的值大约是 ($2\sqrt{2\lfloor\log_2(x)\rfloor}+$常数)，

还有没有更优的策略呢？

mathe

第一次取$a_0=2=2^{2^0}$,
如果第k次和$a_{k-1}$比较，提示大于$a_{k-1}$,取$a_k=a_{k-1}^2$,直到某个$a_n=2^{2^n}$使得$a^{n-1}<x<a_n$
这个步骤共花费不超过$\log_2\log_2(x)+1$次。
然后设$2^{u_1}<x<2^{v_1}$
我们选择$m_1=\lfloor{u_1+v_1}/2\rfloor$,然后将x和$2^{m_1}$进行比较,如果$x<m_1$选择$u_2=u_1,v_2=m_1$;不然选择$u_2=m_1,v_2=v_1$, 依次下去，直到$v_h=u_h+1$.
这个步骤花费$\log_2(v_1-u_1)=\log_2 2^{n-1}=n-1 ~= \log_2\log_2(x)$
所以我们大概经过$2\log_2\log_2(x)$找到$u_h$使得，$2^u_h\le x\lt 2^{u_h+1}$
后面通过二分法，最多再经过$\log_2 2^{u_h}\lt log_2 x$步可得

KeyTo9_Fans

额外的猜数次数，我要$O(\sqrt{\log(x)})$次，

你竟然只需 ($2\log_2\log_2(x)$+常数) 次，太厉害了吧？

按照你这种思路，总猜数次数最终是不是可以优化成

常数 $+\log_2(x)+\log_2\log_2(x)+\log_2\log_2\log_2(x)+\log_2\log_2\log_2\log_2(x)+$......

呢？