Past exam of the year 1 of the computer science course of the University of Oxford / 2021 / Imperative programming (resit) / 2 / c

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 givesFor $n=2^k-1$, the successful-search decision tree has $2^d$ targets at depth $d$, requiring $d+1$ iterations. ThusThe 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$ givesThe base $k=1,n=1$ gives one iteration, as required.