= Solution
The expected saving on the specified successful searches is
$$
k-e_n=\boxed{1-\frac{k}{n}},
$$
which tends to one iteration as $n=2^k-1$ increases. The fractional saving is $1/k-1/n$, which tends to zero. \b[Both versions have logarithmic expected time, and the improvement is a bounded average saving rather than a change of growth rate.] A target at the first middle position benefits greatly, but the <uniform distribution> does not concentrate on that event. The extra equality branch and machine-level costs also matter when comparing measured execution times.
\Image[/past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2021/imperative-programming-resit-search-iterations.png]
{title=Early equality return saves less than one iteration on average in perfect search arrays}
{description=Original exact iteration counts and their difference for uniformly chosen present targets in arrays of length $2^k-1$. The curves describe loop iterations, not measured execution time.}
Back to article page
