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

The expected number is exactly $k$. In the boundary-search version, an interval of length $2^j-1$ is reduced to length $2^{j-1}-1$ whichever comparison branch is taken. It must therefore take exactly $k$ iterations to reduce length $2^k-1$ to zero, including when a probe has already equaled the target. The result holds for every target in this case, so averaging does not change it.