Closed-form for exact number of iterations of binary search

Question

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$.

• codeR: Is there any particular reason you are looking for the exact number? This quantity is not dependent on the search key value but rather on the position $k$ of the key in the sorted array, which can only be found after the search terminates. I am wondering what could be the use case for such a number.
• Electro: I'm writing a paper on algorithm analysis, and it would be nice (but not necessary) if I could find a nice characterization of the number of three-way comparisons used by binary search as a function of its input.
• codeR: Shouldn't an average numbe suffice?
• Electro: The average is a description in terms of input size, not input. (It is also not a characterization of the number of three-way comparisons.)
• D.W.: Cross-posted: cstheory.stackexchange.com/q/54403/5038. Please do not post the same question on multiple sites.