information:classification
Successful searches

In the binary tree representation, a successful search can be represented by a path from the root to the target node, called an internal path. The length of a path is the number of edges (connections between nodes) that the path passes through. The number of iterations performed by a search, given that the corresponding path has length l {\displaystyle l}, is l + 1 {\displaystyle l+1} counting the initial iteration. The internal path length is the sum of the lengths of all unique internal paths. Since there is only one path from the root to any single node, each internal path represents a search for a specific element. If there are n {\displaystyle n} elements, which is a positive integer, and the internal path length is I (n) {\displaystyle I(n)}, then the average number of iterations for a successful search T (n) = 1 + I (n) n {\displaystyle T(n)=1+{\frac {I(n)}{n}}}, with the one iteration added to count the initial iteration.

Since binary search is the optimal algorithm for searching with comparisons, this problem is reduced to calculating the minimum internal path length of all binary trees with n {\displaystyle n} nodes, which is equal to:

I (n) = ∑ k = 1 n ⌊ log 2 (k) ⌋ {\displaystyle I(n)=\sum _{k=1}^{n}\left\lfloor \log _{2}(k)\right\rfloor }

For example, in a 7-element array, the root requires one iteration, the two elements below the root require two iterations, and the four elements below require three iterations. In this case, the internal path length is:

∑ k = 1 7 ⌊ log 2 (k) ⌋ = 0 + 2 (1) + 4 (2) = 2 + 8 = 10 {\displaystyle \sum _{k=1}^{7}\left\lfloor \log _{2}(k)\right\rfloor =0+2(1)+4(2)=2+8=10}

The average number of iterations would be 1 + 10 7 = 2 3 7 {\displaystyle 1+{\frac {10}{7}}=2{\frac {3}{7}}} based on the equation for the average case. The sum for I (n) {\displaystyle I(n)} can be simplified to:

I (n) = ∑ k = 1 n ⌊ log 2 (k) ⌋ = (n + 1) ⌊ log 2 (n + 1) ⌋ − 2 ⌊ log 2 (n + 1) ⌋ + 1 + 2 {\displaystyle I(n)=\sum _{k=1}^{n}\left\lfloor \log _{2}(k)\right\rfloor =(n+1)\left\lfloor \log _{2}(n+1)\right\rfloor -2^{\left\lfloor \log _{2}(n+1)\right\rfloor +1}+2}

Substituting the equation for I (n) {\displaystyle I(n)} into the equation for T (n) {\displaystyle T(n)}:

T (n) = 1 + (n + 1) ⌊ log 2 (n + 1) ⌋ − 2 ⌊ log 2 (n + 1) ⌋ + 1 + 2 n = ⌊ log 2 (n) ⌋ + 1 − (2 ⌊ log 2 (n) ⌋ + 1 − ⌊ log 2 (n) ⌋ − 2) / n {\displaystyle T(n)=1+{\frac {(n+1)\left\lfloor \log _{2}(n+1)\right\rfloor -2^{\left\lfloor \log _{2}(n+1)\right\rfloor +1}+2}{n}}=\lfloor \log _{2}(n)\rfloor +1-(2^{\lfloor \log _{2}(n)\rfloor +1}-\lfloor \log _{2}(n)\rfloor -2)/n}

For integer n {\displaystyle n}, this is equivalent to the equation for the average case on a successful search specified above.