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 $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)=1+{\frac {E(n)}{n}}$, with the one iteration added to count the initial iteration.

This problem can similarly be reduced to determining the minimum external path length of all binary trees with $n$ nodes. In a tree with minimum external path length, all external nodes are within the last two levels of the extended binary tree. This is equivalent to an unsuccessful search ending in either the second-deepest or deepest level of the tree depending on the location of the target node.

In particular, let $l(n)$ be the number of iterations in the worst case, or the number of levels in the extended binary tree, $l(n)=\lfloor \log _{2}(n)+1\rfloor$. Then, there are $2^{l(n)}-n$ nodes in the second-deepest level of the tree (level $l(n)-1$) and $2n-2^{l(n)}$ nodes in the deepest level of the tree (level $l(n)$). Therefore,

$E(n)=(l(n)-1)(2^{l(n)}-n)+l(n)(2n-2^{l(n)})=(l(n)+1)n-2^{l(n)}=(n+1)(l(n)+1)-2^{l(n)}$