Editing Binary search (section)

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