<p>(This is a cross-post from <a href="https://cs.stackexchange.com/questions/168242/closed-form-for-exact-number-of-iterations-of-binary-search">CS.SE</a>).</p>
<p>Consider a sorted list of <span class="math-container">$n$</span> elements <span class="math-container">$x_1, \ldots, x_n$</span>. Using binary search to find <span class="math-container">$x_k$</span> in this list takes <span class="math-container">$f(n, k)$</span> iterations, where <span class="math-container">$f : \mathbb{N}^2 \to \mathbb{N}$</span> is a function such that, for all <span class="math-container">$n, k \in \mathbb{N}$</span> such that <span class="math-container">$1 \leq k \leq n$</span>,
<span class="math-container">$$
f(n, k) = \begin{cases}
1, &amp; k = m,\\
1 + f(n - m, k - m), &amp; k &gt; m,\\
1 + f(m - 1, k), &amp; k &lt; m,
\end{cases}
$$</span>
where <span class="math-container">$m = \lfloor (1 + n)/2 \rfloor$</span>.</p>
<p>Is there a closed-form expression for <span class="math-container">$f(n, k)$</span>, or at least a nice non-recursive formula?</p>
<p>Looking at the decision tree for the binary search, it is easy to see that <span class="math-container">$f(n, k) = d + 1$</span> where <span class="math-container">$d$</span> is the depth of <span class="math-container">$x_k$</span> 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 <span class="math-container">$k$</span> with division and multiplication. My hypothesis was that <span class="math-container">$d$</span> was the least value such that <span class="math-container">$k = \left\lfloor \frac{na}{2^{d+1}} \right\rfloor$</span> for some positive integer <span class="math-container">$a &lt; n$</span>, but that doesn't work for <span class="math-container">$n = 10, k = 3$</span>.</p>

CC BY-SA 4.0
2024-06-14T22:57:24.343Z
If $n=2^t-1$ for some $t\in\mathbb{N}$, and $k=2^rs$ where $s$ is odd, then $f(n,k)$ is $t-r$. I really doubt there exists any non-recursive formula for a general $n$
EnEm
CC BY-SA 4.0
2024-06-15T02:18:08.960Z
Flajolet and Golin, ICALP '93 (https://algo.inria.fr/flajolet/Publications/FlGo93.pdf), studied questions of this form (they did it for mergesort, but I'd be shocked if their techniques didn't work for binary search, though I haven't thought about it myself).
Joshua Grochow
<ds.algorithms>
Closed-form for exact number of iterations of binary search
Electro
# Closed-form for exact number of iterations of binary search

(Asked by: username_0 on 2024-06-14)

(This is a cross-post from [CS.SE](https://cs.stackexchange.com/questions/168242/closed-form-for-exact-number-of-iterations-of-binary-search)).

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

**Tags:** ds.algorithms
> **Comments:**
> **username_1**: If $n=2^t-1$ for some $t\in\mathbb{N}$, and $k=2^rs$ where $s$ is odd, then $f(n,k)$ is $t-r$. I really doubt there exists any non-recursive formula for a general $n$  
> **username_2**: Flajolet and Golin, ICALP '93 (https://algo.inria.fr/flajolet/Publications/FlGo93.pdf), studied questions of this form (they did it for mergesort, but I'd be shocked if their techniques didn't work for binary search, though I haven't thought about it myself).  

---

## 0 answers

