(This is a cross-post from CS.SE).
Consider a sorted list of $n$ elements $x_1, \ldots, x_n$. Using binary search to find $x_k$ in this list takes $f(n, k)$ iterations, where $f : \mathbb{N}^2 \to \mathbb{N}$ is a function such that, for all $n, k \in \mathbb{N}$ such that $1 \leq k \leq n$, $$ f(n, k) = \begin{cases} 1, & k = m,\\ 1 + f(n - m, k - m), & k > m,\\ 1 + f(m - 1, k), & k < m, \end{cases} $$ where $m = \lfloor (1 + n)/2 \rfloor$.
Is there a closed-form expression for $f(n, k)$, or at least a nice non-recursive formula?
Looking at the decision tree for the binary search, it is easy to see that $f(n, k) = d + 1$ where $d$ is the depth of $x_k$ in the decision tree, but I didn't get much further. The repeated floored division by 2 made me think it has something to do with approximating $k$ with division and multiplication. My hypothesis was that $d$ was the least value such that $k = \left\lfloor \frac{na}{2^{d+1}} \right\rfloor$ for some positive integer $a < n$, but that doesn't work for $n = 10, k = 3$.
