Solution
= Solution
\b[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.