What is the first historical reference to the binary search algorithm?

Question

Most of you know what I mean, but I will define it broadly: the binary search algorithm consists in searching iteratively for an element within an ordered set, by asking yes/no questions that will exclude about half of the remaining elements each loop, until there remains only a possible element. For example "think of a number between 1 and 100; is it bigger than 50? > no; is it bigger than 25? yes; is it bigger than 37?" and so on.

This algorithm is probably as old as child games, but there must be a first historical reference to it. Which one?

Answer 1

In "The Art of Computer Programming, Vol 3, second edition, p422", it is said:

Binary search was first first mentioned by John Mauchly, in what was perhaps the first published discussion of nonnumerical programming methods [Theory and Techniques for the dsign of Electronic Digital computers, edited by G.W. Patterson, 1 (1946), 9.7-9.8; 3 (1946),22.8-22.9]. The method became well known to programmers, but nobody seems to have worked out the details of what should be done when N does not have the special form $2^n-1$. [See A.D.Booth, Nature 176 (1955), 565; A. I. Dumey, Computers and Automation 5 (December 1956), 7, where binary search is called "Twenty Questions"; Daniel D. McCracken, Digital Computer Programming (Wiley, 1957), 201-203; and M. Halpern, CACM 1, 1 (February 1958), 1-3.]

D.H.Lehmer [Proc. Symp. Appl. Math. 10 (1960), 180-181] was apparently the first to publish a binary search algorithm that works for all N. [...]

Binary trees similar to Fibonacci trees appeared in the pioneering work of the Norwegian mathematician Axel Thue as early as 1910.

On Google Scholar, the oldest article that I could find that has a reference to the binary search algorithm seems to be an article of 1962 by Thomas N. Hibbard called "Some Combinatorial Properties of Certain Trees With Applications to Searching and Sorting". I do not have access to the full text, but according to google it is said inside the article

The well-known binary search algorithm [...]

Answer 2

In Jataka, there's a story about Losaka http://www.sacred-texts.com/bud/j1/j1044.htm

So in time it came to pass that the people fell into a wretched plight. Reflecting that such had not been their lot in former days, but that now they were going to rack and ruin, they concluded that there must be some breeder of misfortune among them, and resolved to divide into two bands. This they did; and there were then two bands of five hundred families each. Thence-forward, ruin dogged the band which included the parents of the future Losaka, whilst the other five hundred families throve apace. So the former resolved to go on halving their numbers, and did so, until this one family was parted from all the rest. Then they knew that the breeder of misfortune was in that family, and with blows drove them away

Answer 3

The method of bisection was used over three hundred years before Bolzano, to prove the intermediate value theorem by Simon Stevin, in the case of a particular cubic polynomial (of course Stevin did not use the term "binary search"). For details see this 2012 publication in Foundations of Science.

Answer 4

Like skysurf I could not find any ancient record for binary search, so this is more of an extended comment. The problem may be that before computer science algorithms were either practical, or games for mathematically inclined, and the binary search wasn't attractive either practically or recreationally. Of course, if we cast the net wider something ancient can be found. Already Plato and Aristotle constructed classifications based on binary dichotomies, which were later depicted as binary Porphyrian trees, and reincarnated in computer science as sorted binary trees, that are custom made for binary searches.

A closer relative concerns continuous cousin of binary search, the method of bisection. It appears that it was used by Bolzano in 1817 to prove the intermediate value property (but see Mikhail's comment below on Stevin's prior use), and the numerical method based on it was developed shortly thereafter. To find a zero of a continuous function on an interval where it takes values of opposite signs at the ends one bisects the interval, takes the subinterval with opposite signs, bisects again, etc. Unlike binary search bisection may never halt, but it converges to a zero, and produces approximations with obvious error bounds at each step.

Unfortunately, I could not find an early reference for a yes/no number guessing game, although "think of a number" tricks with extra information occur as early as the Rhind papyrus (c. 1800 BC). When extra information is provided on how badly a guess fails, even in a simple form like cold/warmer/hot, it is also inefficient since it doesn't take it into account. The same goes for bisection, if we take into account end values rather than just signs double false position converges much faster for practically relevant functions. And it is indeed ancient, occurring already in Chinese Nine Chapters from before 220 AD.