= Solution
For an <array> of size $2n+1$, the first probe finds the uniformly selected target with <probability> $1/(2n+1)$. Otherwise it leaves a half of size $n$; conditional on entering that half, its target is uniform there. Counting the first iteration in every case gives
$$
e_{2n+1}=1+\frac{2n}{2n+1}e_n.
$$
For $n=2^k-1$, the successful-search decision tree has $2^d$ targets at depth $d$, requiring $d+1$ iterations. Thus
$$
e_n=\frac{\sum_{d=0}^{k-1}(d+1)2^d}{2^k-1}.
$$
The numerator is $(k-1)2^k+1$, as follows by <induction> or by shifting and subtracting a finite geometric sum. Substituting $2^k=n+1$ gives
$$
\boxed{e_n=k-1+\frac{k}{n},\qquad a=-1,\quad b=1.}
$$
The base $k=1,n=1$ gives one iteration, as required.
Back to article page
