Editing Binary search (section)

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