Average successful search in a perfect binary search tree ($e_{2^k-1}=k-1+\frac{k}{2^k-1}$)

For $n=2^k-1$ distinct keys and a uniformly chosen present target, early-return binary search takes mean $k-1+k/n$ iterations. There are $2^d$ targets needing $d+1$ probes, so sum $(d+1)2^d$ over depths zero through $k-1$ and divide by $n$. A boundary search that always closes the interval takes exactly $k$ iterations. Their expected difference is $1-k/n<1$, even though an individual shallow target can save many probes.