Editing Binary search (section)

== Implementation issues ==
{{Blockquote|Although the basic idea of binary search is comparatively straightforward, the details can be surprisingly tricky|[[Donald Knuth]]{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "Binary search"}} }}

When [[Jon Bentley (computer scientist)|Jon Bentley]] assigned binary search as a problem in a course for professional programmers, he found that ninety percent failed to provide a correct solution after several hours of working on it, mainly because the incorrect implementations failed to run or returned a wrong answer in rare [[edge case]]s.{{Sfn|Bentley|2000|loc=§4.1 ("The Challenge of Binary Search")}} A study published in 1988 shows that accurate code for it is only found in five out of twenty textbooks.<ref name="textbook">{{cite journal | first = Richard E. | last = Pattis | author-link1=Richard E. Pattis| doi = 10.1145/52965.53012 | title = Textbook errors in binary searching | journal = SIGCSE Bulletin | volume = 20 | year = 1988 | pages = 190–194 }}</ref> Furthermore, Bentley's own implementation of binary search, published in his 1986 book ''Programming Pearls'', contained an [[Integer overflow|overflow error]] that remained undetected for over twenty years.  The [[Java (programming language)|Java programming language]] library implementation of binary search had the same overflow bug for more than nine years.<ref>{{cite web | url = http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html | title = Extra, extra – read all about it: nearly all binary searches and mergesorts are broken | work = Google Research Blog | first = Joshua | last = Bloch | author-link1 = Joshua Bloch | date = 2 June 2006 | access-date = 21 April 2016 | archive-url = https://web.archive.org/web/20160401140544/http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html | archive-date = 1 April 2016 | url-status = live | df = dmy-all }}</ref>

In a practical implementation, the variables used to represent the indices will often be of fixed size (integers), and this can result in an [[integer overflow|arithmetic overflow]] for very large arrays. If the midpoint of the span is calculated as <math>\frac{L+R}{2}</math>, then the value of <math>L+R</math> may exceed the range of integers of the data type used to store the midpoint, even if <math>L</math> and <math>R</math> are within the range. If ''<math>L</math>'' and ''<math>R</math>'' are nonnegative, this can be avoided by calculating the midpoint as <math>L+\frac{R-L}{2}</math>.<ref name="semisum">{{cite journal|last1=Ruggieri|first1=Salvatore|title=On computing the semi-sum of two integers|journal=[[Information Processing Letters]]|date=2003|volume=87|issue=2|pages=67–71|doi=10.1016/S0020-0190(03)00263-1|url=http://www.di.unipi.it/~ruggieri/Papers/semisum.pdf|citeseerx=10.1.1.13.5631|access-date=19 March 2016|archive-url=https://web.archive.org/web/20060703173514/http://www.di.unipi.it/~ruggieri/Papers/semisum.pdf|archive-date=3 July 2006|url-status=live|df=dmy-all}}</ref>

An infinite loop may occur if the exit conditions for the loop are not defined correctly. Once ''<math>L</math>'' exceeds ''<math>R</math>'', the search has failed and must convey the failure of the search. In addition, the loop must be exited when the target element is found, or in the case of an implementation where this check is moved to the end, checks for whether the search was successful or failed at the end must be in place. Bentley found that most of the programmers who incorrectly implemented binary search made an error in defining the exit conditions.<ref name="Bottenbruch1962" />{{Sfn|Bentley|2000|loc=§4.4 ("Principles")}}