[算法求助] 如何快速猜到 upper limit

[melonux]

给定两个整数 a, b, 其中 a<=b. 给定一个函数, bool is_greater(int c), 当 c>b 时返回 true. 告知 a, 要猜 b, 怎么做最有效?

brute force 的话, 就是让 c=a, 逐渐+1, 直到is_greater(c)==false, 则 b=c-1

更具体一些. b 就在 uint_32 的范围内. 最有效指的是调用 is_greater 函数的次数的期望值最小.

再限定一下. 那就给个指数分布吧. 用意是 b 更可能出现在离 a 较近的地方. pdf(b-a)=exp(-(b-a))

上面两条有冲突. 那就分两种情况吧.
1. b <= uint32_max. b 在(a, uint32_max] 上取值服从均匀分布
2. b 无上限. b 在(a, +Inf) 上取值服从指数分布

给出任意一种情况的最优解都行. 最好有推理证明或思路. 渐进 /次优解也是可以的. 反正就是想看看各种新奇的方法.

[thedrwu]

二分

[lance6716]

Exponential search

[nanaw]

得有个 b 最大的可能范围才能二分吧。这样无限大怎么猜。。

[geelaw]

如果你假设 int 是有限范围，可以直接二分，甚至不需要知道 a。

如果你假设 int 是无限范围且 a < 0，则先通过测试 -1、0 确定 b 的符号；如果 b 是负数，则你已经有上下界，用二分；如果 b 是 0，则结束；如果 b 是正数，则不断测试一个数是否是上界，直到找到上下界，再用二分。

你需要定义什么叫做“最有效”，才能决定如何询问“最有效” 。

[Kirscheis]

先指数前进，然后二分即可

[rrfeng]

如果我操作的话选指数前进，再二分定位。

但实际上感觉可以算出来期望次数

[melonux]

@nanaw 肯定有限大啊, 都是给定值了. 不需要预先假设 b-a 的范围的.

[melonux]

@geelaw 好的. 更具体一些. b 就在 uint_32 的范围内. 最有效指的是调用 is_greater 函数的次数的期望值最小.

[melonux]

@lance6716 嗯. 很有价值

[geelaw]

@melonux #8 你仍然没有定义好什么叫“最有效”，你没有指定固定 a 后 b 的条件分布。

一旦有了这个分布，你可以做动态规划来算出最佳策略。

[melonux]

嗯. 您这个考虑更加精细了. 那就给个指数分布吧. 用意是 b 更可能出现在离 a 较近的地方. pdf(b-a)=exp(-(b-a))

[melonux]

@geelaw 很想知道这个怎么动态规划

[lance6716]

@melonux 指数分布是无记忆的（不知道在这个离散程度和规模下能不能这么概括），给定搜索的区间[low, high]，只跟区间长度有关

均匀分布的时候二分中点。不均匀就二分“累计概率达到一半”的那个点

[melonux]

@lance6716 嗯. 您说的对. 给定范围和给定这个分布本身冲突了. 我的本意是均匀分布即可. 但看到那个可以动态规划的方法, 就很好奇. 想看到一个不平凡的解, 所以给了一个不均匀的分布.

[geelaw]

@melonux #12 如果是均匀分布显然二分法就是动态规划会给出的解。如果是几何分布，不妨设 a=0 （其他情况把各数虚拟地加上 -a 即可），用 f(x) 表示上界是 c 时（也就是范围是 (0, x]）最小期望次数，那么

f(1) = 0
f(n) = 1 + min ( Pr[b>c] f(n-c) + Pr[b<=c] f(c) )

对于初始无上界的情况，这是一个 Markov 链，因此有

f(infty) = 1 + inf ( Pr[b>c] f(infty) + Pr[b<=c] f(c) )

f(infty) = inf (1/Pr[b<=c] + f(c))

利用有限值的 f 的情况算出最佳的 c。