© 1983 by British Computer Society
Some Lessons Drawn from the History of the Binary Search Algorithm
Institut d'Informatique, Rue Grandgagnage, Namur, Belgium
The paper's aim is to study the behaviour of 26 programmers who designed a binary search algorithm; for each of them, we try to point out the correct or erroneous reasoning, that yielded the algorithm. To do this, we first analyse 4 typical correct algorithms in an informal and intuitive way, discussing the probable reasons why the programmers developed the algorithms as they did; these are, namely: (1) a uniform binary search algorithm on a monotonically increasing sequence of T terms, T=2n–1, n
1; (2) a uniform binary search algorithm on a monotonically increasing sequence of T terms; (3) a binary search algorithm with ‘two-way tests’ on a monotonically increasing sequence of T terms, T1; (4) a general binary search algorithm on a monotonically increasing sequence of T terms. Then, the important errors found in the 26 published algorithms are pointed out, with an attempt at discussing why these errors were made. Three lessons can be drawn from the history of the binary search algorithm, which we believe are applicable to many other algorithms, namely (1) there is a continuous progression by programmers towards a highest possible degree of generality; (2) programs built with optimization concerns in mind have no better mean execution time than the most general ones; (3) the distribution of errors among families of algorithms is not uniform.
Received July 1982.
* Institut d'Informatique, Rue Grandgagnage 21, B-5000 Namur, Belgium