Editing Binary search (section)

== History ==
The idea of sorting a list of items to allow for faster searching dates back to antiquity. The earliest known example was the Inakibit-Anu tablet from Babylon dating back to {{circa|200 BCE}}. The tablet contained about 500 [[sexagesimal]] numbers and their [[Multiplicative inverse|reciprocals]] sorted in [[lexicographical order]], which made searching for a specific entry easier. In addition, several lists of names that were sorted by their first letter were discovered on the [[Aegean Islands]]. ''[[Catholicon (1286)|Catholicon]]'', a Latin dictionary finished in 1286 CE, was the first work to describe rules for sorting words into alphabetical order, as opposed to just the first few letters.{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "History and bibliography"}}

In 1946, [[John Mauchly]] made the first mention of binary search as part of the [[Moore School Lectures]], a seminal and foundational college course in computing.{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "History and bibliography"}} In 1957, [[W. Wesley Peterson|William Wesley Peterson]] published the first method for interpolation search.{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "History and bibliography"}}<ref>{{cite journal |last1=Peterson |first1=William Wesley |author-link=W. Wesley Peterson|title=Addressing for random-access storage |journal=IBM Journal of Research and Development |date=1957 |volume=1 |issue=2 |pages=130–146 |doi=10.1147/rd.12.0130}}</ref> Every published binary search algorithm worked only for arrays whose length is one less than a power of two{{efn|That is, arrays of length 1, 3, 7, 15, 31 ...<ref>"2<sup>''n''</sup>&minus;1". [[On-Line Encyclopedia of Integer Sequences|OEIS]] [http://oeis.org/A000225 A000225] {{Webarchive|url=https://web.archive.org/web/20160608084228/http://oeis.org/A000225 |date=8 June 2016 }}.  Retrieved 7 May 2016.</ref>}} until 1960, when [[Derrick Henry Lehmer]] published a binary search algorithm that worked on all arrays.<ref>{{cite book | author=Lehmer, Derrick | title=Combinatorial Analysis | chapter=Teaching combinatorial tricks to a computer | series=Proceedings of Symposia in Applied Mathematics | year=1960 | volume=10 | pages=180–181 | doi=10.1090/psapm/010/0113289| isbn=9780821813102 | doi-access=free |mr=0113289}}</ref> In 1962, Hermann Bottenbruch presented an [[ALGOL 60]] implementation of binary search that placed the [[#Alternative procedure|comparison for equality at the end]], increasing the average number of iterations by one, but reducing to one the number of comparisons per iteration.<ref name="Bottenbruch1962" /> The [[#Uniform binary search|uniform binary search]] was developed by A. K. Chandra of [[Stanford University]] in 1971.{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "History and bibliography"}} In 1986, [[Bernard Chazelle]] and [[Leonidas J. Guibas]] introduced [[fractional cascading]] as a method to solve numerous search problems in [[computational geometry]].<ref name="ChazelleLiu2001" /><ref>{{cite journal | last1 = Chazelle | first1 = Bernard | author-link1 = Bernard Chazelle| last2 = Guibas | first2 = Leonidas J. | s2cid = 12745042 | author-link2 = Leonidas J. Guibas| title = Fractional cascading: I. A data structuring technique| journal = [[Algorithmica]]| volume = 1 | issue = 1–4 | year = 1986 | pages = 133–162 | doi = 10.1007/BF01840440| url = http://www.cs.princeton.edu/~chazelle/pubs/FractionalCascading1.pdf| citeseerx = 10.1.1.117.8349 }}</ref><ref>{{citation| last1 = Chazelle | first1 = Bernard | author-link1 = Bernard Chazelle| last2 = Guibas | first2 = Leonidas J. | s2cid = 11232235 | author-link2 = Leonidas J. Guibas| title = Fractional cascading: II. Applications| journal = [[Algorithmica]]| volume = 1 | issue = 1–4 | year = 1986 | pages = 163–191 | doi = 10.1007/BF01840441| url = http://www.cs.princeton.edu/~chazelle/pubs/FractionalCascading2.pdf}}</ref>