User:Esquivalience/sandbox

Derivation of average case

The average number of iterations performed by binary search depends on the probability of each element being searched. The average case is different for successful searches and unsuccessful searches. It will be assumed that each element is equally likely to be searched for successful searches. For unsuccessful searches, it will be assumed that the intervals between and outside elements are equally likely to be searched. The average case for successful searches is the number of iterations required to search every element exactly once, divided by $n$, the number of elements. The average case for unsuccessful searches is the number of iterations required to search an element within every interval exactly once, divided by the $n+1$ intervals. (Knuth 1998, §6.2.1 ("Searching an ordered table"), subsection "Further analysis of binary search".)

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$, is $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$ elements, which is a positive integer, and the internal path length is $I(n)$, then the average number of iterations for a successful search $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$ nodes, which is equal to:

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

$\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+{\frac {10}{7}}=2{\frac {3}{7}}$ based on the equation for the average case. The sum for $I(n)$ can be simplified to:

$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)$ into the equation for $T(n)$:

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

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

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

Unsuccessful searches

Unsuccessful searches can be represented by augmenting the tree with external nodes, which forms an extended binary tree. If an internal node, or a node present in the tree, has fewer than two child nodes, then additional child nodes, called external nodes, are added so that each internal node has two children. By doing so, an unsuccessful search can be represented as a path to an external node, whose parent is the single element that remains during the last iteration. An external path is a path from the root to an external node. The external path length is the sum of the lengths of all unique external paths. If there are $n$ elements, which is a positive integer, and the external path length is $E(n)$, then the average number of iterations for an unsuccessful search $T'(n)={\frac {E(n)}{n+1}}$, with the one iteration added to count the initial iteration. The external path length is divided by $n+1$ instead of $n$ because there are $n+1$ external paths, representing the intervals between and outside the elements of the array.

This problem can similarly be reduced to determining the minimum external path length of all binary trees with $n$ nodes. For all binary trees, the external path length is equal to the internal path length plus $2n$. Substituting the equation for $I(n)$:

$E(n)=I(n)+2n=\left[(n+1)\left\lfloor \log _{2}(n+1)\right\rfloor -2^{\left\lfloor \log _{2}(n+1)\right\rfloor +1}+2\right]+2n=(n+1)(\lfloor \log _{2}(n)\rfloor +2)-2^{\lfloor \log _{2}(n)\rfloor +1}$

Substituting $E(n)$ into the equation for $T'(n)$, the average case for unsuccessful searches can be determined:

$T'(n)={\frac {(n+1)(\lfloor \log _{2}(n)\rfloor +2)-2^{\lfloor \log _{2}(n)\rfloor +1}}{(n+1)}}=\lfloor \log _{2}(n)\rfloor +2-2^{\lfloor \log _{2}(n)\rfloor +1}/(n+1)$