Concepts

Binary Search

Also Known As Half-Interval Search

Algorithm

Citation Formats

General Reference

Computing Atlas. "Binary Search." Accessed August 30, 2026. https://dev-computing.interactiveatlas.org/concepts/binary-search.

APA Style

Computing Atlas. (n.d.). Binary Search. Retrieved August 30, 2026, from https://dev-computing.interactiveatlas.org/concepts/binary-search

BibTeX

@misc{computingatlas-binary-search,
  author = {Computing Atlas},
  title = {Binary Search},
  year = {2026},
  url = {https://dev-computing.interactiveatlas.org/concepts/binary-search},
  note = {Accessed August 30, 2026}
}

Binary search is a search algorithm that finds the position of a target value within a sorted array by repeatedly halving the portion that could contain it. It runs in logarithmic time in the worst case, making O(log n) comparisons for n elements, which is why keeping data sorted pays: a million entries need about twenty questions, not a million. Deceptively simple, it is a famous source of subtle implementation errors, and a variant omitting one check was first published correctly by Hermann Bottenbruch in 1962.

Facts

Origin Year

1946 1

John Mauchly described the basic idea in 1946, but the first correctly published bug-free binary search algorithm did not appear until 1962 (Hermann Bottenbruch); Donald Knuth cites this gap as a famous case of a simple idea being surprisingly tricky to implement correctly.

Core Principle

Halve the search space with every comparison: ask of the middle element whether the target lies before or after it, and discard the half that cannot contain it. 1

Cross-Tradition Connections