← 完整题目索引

PROJECT EULER · #0527

随机二分查找

Randomized Binary Search

仅题目 · 待解原题 ↗

在 1≤t≤n 范围内随机选择一个秘密整数 t。

目标是通过整数 g 进行重复猜测来猜测 t 的值。做出猜测后,有​​三种可能的结果,其中将显示 g<t、g=t 或 g>t。然后可以根据需要重复该过程。

通常,可以通过二分搜索最小化平均所需的猜测次数:给定下限 L 和上限 H(初始化为 L=1 和 H=n),令 g=⌊(L+H)/2⌋ 其中 ⌊⋅⌋ 是整数下取整函数。如果g=t,则过程结束。否则,如果 g<t,则设置 L=g+1,但如果 g>t,则设置 H=g−1。设置新边界后,搜索过程会重复,并最终在找到 t 后结束。即使无需搜索即可推导出 t,也假设无论如何都需要搜索来确认该值。

你的朋友 Bob 认为标准二分搜索并不比他的随机变体好多少:不要设置 g=⌊(L+H)/2⌋,只需让 g 为 L 和 H 之间的随机整数(含)。该算法的其余部分与标准二分搜索相同。这个新的搜索例程将被称为随机二分搜索。

假设随机 t 为 1≤t≤n,令 B(n) 为使用标准二分搜索找到 t 所需的预期猜测次数,并令 R(n) 为使用随机二分搜索找到 t 所需的预期猜测次数。例如,四舍五入到小数点后 8 位时,B(6)=2.33333333 和 R(6)=2.71666667。

求 R(1010)−B(1010) 四舍五入到 8 小数位。

题解待补充

这道题的题目已收录,解题思路、代码和答案将在后续补充。