Project Euler Problem 527
A secret integer t is selected at random within the range 1 le t le n.
Solution
Answer: 11.92412011
Let:
- $B(n)$ = expected number of guesses using standard binary search.
- $R(n)$ = expected number of guesses using random binary search.
For the randomized version, if the current interval has size $n$, choosing a random pivot $g$ gives:
$$R(n)=1+\frac{1}{n^2}\sum_{g=1}^{n} \left((g-1)R(g-1)+(n-g)R(n-g)\right)$$
Using symmetry and defining $S(n)=\sum_{k=1}^{n} kR(k)$, this simplifies to:
$$R(n)=1+\frac{2S(n-1)}{n^2}$$
and
$$S(n)=\left(1+\frac{2}{n}\right)S(n-1)+n$$
This telescopes to the closed form:
$$R(n)=1+\frac{2(n+1)}{n} \left(H_n+\frac{2}{n+1}-2\right)$$
where $H_n$ is the harmonic number.
For standard binary search:
$$B(n) = 1+\frac{aB(a)+bB(b)}{n}$$
with
$$a=\left\lfloor \frac{n-1}{2}\right\rfloor,\qquad b=n-1-a$$
This only requires $O(\log n)$ memoized recursion.
Evaluating at $n=10^{10}$:
$$R(10^{10}) \approx 44.20613319450459$$
$$B(10^{10}) \approx 32.28201308510000$$
Hence:
$$R(10^{10})-B(10^{10}) \approx 11.92412010940459$$
Rounded to 8 decimal places:
Answer: 11.92412011