ML Anthology

The Origin of the Binary-Search Paradigm

Zohar Manna, Richard J. Waldinger
IJCAI 1985 pp. 222-224
doi:10.1016/0167-6423(87)90025-6 /ijcai/1985/manna1985ijcai-origin/

Abstract

In a binary-search algorithm for the computation of a numerical function, the interval in which the desired output is sought is divided in half at each iteration. The paper considers how such algorithms might be derived from their specifications by an automatic system for program synthesis. The derivation of the binary-search concept has been found to be surprisingly straight-forward. The programs obtained, though reasonably simple and efficient, are quite different from those that would have been constructed by informal means.

PDF Semantic Scholar

Cite

Text

Manna and Waldinger. "The Origin of the Binary-Search Paradigm." International Joint Conference on Artificial Intelligence, 1985. doi:10.1016/0167-6423(87)90025-6

Markdown

[Manna and Waldinger. "The Origin of the Binary-Search Paradigm." International Joint Conference on Artificial Intelligence, 1985.](https://mlanthology.org/ijcai/1985/manna1985ijcai-origin/) doi:10.1016/0167-6423(87)90025-6

BibTeX

@inproceedings{manna1985ijcai-origin,
  title     = {{The Origin of the Binary-Search Paradigm}},
  author    = {Manna, Zohar and Waldinger, Richard J.},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year      = {1985},
  pages     = {222-224},
  doi       = {10.1016/0167-6423(87)90025-6},
  url       = {https://mlanthology.org/ijcai/1985/manna1985ijcai-origin/}
}