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. This description is adapted from Wikipedia contributors under CC BY-SA 4.0; changes were made. https://creativecommons.org/licenses/by-sa/4.0/
Facts
Origin YearJohn 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 PrincipleHalve 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 FAQs
Does the data have to be sorted before binary search works?
Yes; the array must be sorted first.
Yes. The array must be sorted first for binary search to be applied, because each comparison discards the half that cannot contain the target. Binary search is faster than linear search except for small arrays.
Connections
Associated With
John Mauchly, Pioneers John Mauchly described the basic idea of binary search in a 1946 lecture, already the cited source for this concept's own origin-year fact.
Source Wikipedia: Binary search algorithm
In Field
Sources
1. Wikipedia: Binary search algorithm
WikipediaLead section
In computer science, binary search, also known as half-interval search, logarithmic search, or binary chop, is a search algorithm that finds the position of a target value within a sorted array.
Performance section
Binary search runs in logarithmic time in the worst case, making O(log n) comparisons, where n is the number of elements in the array.
Introduction
Binary search compares the target value to the middle element of the array.
History section
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.
- Associated With: John Mauchly
View the Source Binary search (Wikipedia)
In Group: Sorting and Searching Algorithms, LeadQuote, In Group: Sorting and Searching Algorithms, Lead
In computer science, binary search, also known as half-interval search, logarithmic search, or binary chop, is a search algorithm that finds the position of a target value within a sorted array.
Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.