Binary Search definition
Binary search finds a target in a sorted collection by checking the middle and discarding the half that cannot contain it.
Binary Search in a picture
How it works
Compare the middle item with the target. If it matches, stop. If the target is smaller, keep the lower half. If it is larger, keep the upper half. Repeat until you find it or the remaining interval is empty.
Worked examples
Search for 2 in [2, 4, 6, 8, 10]. Which half survives the first comparison?
The lower half, because 2 is smaller than the middle value 6.
What if the middle value equals the target?
Return its position and stop.
Why does the candidate list shrink quickly?
Each unsuccessful midpoint comparison removes about half of the remaining candidates.
Common mistake
Sort the data first or use a search method that allows unsorted data. The midpoint comparison relies on order.
Quick check
How does the candidate range shrink?
Show answer
It is roughly halved at each step.
What growth rate describes the usual worst-case comparison count?
Show answer
Logarithmic, O(log n).
Sources
Flashcard
Binary Search
Reveal the definition
Binary search finds a target in a sorted collection by checking the middle and discarding the half that cannot contain it.
Effortless Math. “Binary Search.” Math Dictionary.
