Editing Binary search (section)

=== 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 [[Interval (mathematics)|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 <math>n</math>, 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 <math>n + 1</math> intervals.{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "Further analysis of binary search"}}

==== Successful searches ====
<!-- E stands for "expected" -->
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 {{mvar|l}}, is <math>l + 1</math> 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 {{mvar|n}} elements, which is a positive integer, and the internal path length is <math>I(n)</math>, then the average number of iterations for a successful search <math>T(n) = 1 + \frac{I(n)}{n}</math>, with the one iteration added to count the initial iteration.{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "Further analysis of binary search"}}

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 {{mvar|n}} nodes, which is equal to:{{Sfn|Knuth|1997|loc=§2.3.4.5 ("Path length")}}

<math display="block">
I(n) = \sum_{k=1}^n \left \lfloor \log_2(k) \right \rfloor
</math>

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:{{Sfn|Knuth|1997|loc=§2.3.4.5 ("Path length")}}

<math display="block">
\sum_{k=1}^7 \left \lfloor \log_2(k) \right \rfloor = 0 + 2(1) + 4(2) = 2 + 8 = 10
</math>

The average number of iterations would be <math>1 + \frac{10}{7} = 2 \frac{3}{7}</math> based on the equation for the average case. The sum for <math>I(n)</math> can be simplified to:{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "Further analysis of binary search"}}

<math display="block">
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
</math>

Substituting the equation for <math>I(n)</math> into the equation for <math>T(n)</math>:{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "Further analysis of binary search"}}

<math display="block">
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
</math>

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

==== 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 <math>n</math> elements, which is a positive integer, and the external path length is <math>E(n)</math>, then the average number of iterations for an unsuccessful search <math>T'(n)=\frac{E(n)}{n+1}</math>, with the one iteration added to count the initial iteration. The external path length is divided by <math>n+1</math> instead of <math>n</math> because there are <math>n+1</math> external paths, representing the intervals between and outside the elements of the array.{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "Further analysis of binary search"}}

This problem can similarly be reduced to determining the minimum external path length of all binary trees with <math>n</math> nodes. For all binary trees, the external path length is equal to the internal path length plus <math>2n</math>.{{Sfn|Knuth|1997|loc=§2.3.4.5 ("Path length")}} Substituting the equation for <math>I(n)</math>:{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "Further analysis of binary search"}}

<math>
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}
</math>

Substituting the equation for <math>E(n)</math> into the equation for <math>T'(n)</math>, the average case for unsuccessful searches can be determined:{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "Further analysis of binary search"}}

<math>
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)
</math>

==== Performance of alternative procedure ====
Each iteration of the binary search procedure defined above makes one or two comparisons, checking if the middle element is equal to the target in each iteration. Assuming that each element is equally likely to be searched, each iteration makes 1.5 comparisons on average. A variation of the algorithm checks whether the middle element is equal to the target at the end of the search. On average, this eliminates half a comparison from each iteration. This slightly cuts the time taken per iteration on most computers. However, it guarantees that the search takes the maximum number of iterations, on average adding one iteration to the search. Because the comparison loop is performed only <math display="inline">\lfloor \log_2 (n) + 1 \rfloor</math> times in the worst case, the slight increase in efficiency per iteration does not compensate for the extra iteration for all but very large <math display="inline">n</math>.{{Efn|{{Harvnb|Knuth|1998}} showed on his [[MIX (abstract machine)|MIX]] computer model, which Knuth designed as a representation of an ordinary computer, that the average running time of this variation for a successful search is <math display="inline">17.5 \log_2 n + 17</math> units of time compared to <math display="inline">18 \log_2 n - 16</math> units for regular binary search. The time complexity for this variation grows slightly more slowly, but at the cost of higher initial complexity.{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "Exercise 23"}}}}{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "Exercise 23"}}<ref>{{cite journal|last1=Rolfe|first1=Timothy J.|s2cid=23752485|title=Analytic derivation of comparisons in binary search|journal=ACM SIGNUM Newsletter|date=1997|volume=32|issue=4|pages=15–19|doi=10.1145/289251.289255|doi-access=free}}</ref>