Algorithms · foundation
Binary search
Binary search locates a target or boundary in an ordered search space by comparing at a midpoint and discarding the half that cannot contain the answer.
Why it matters
Halving reduces a million candidates to about twenty decisions, and the same pattern finds transition points in monotonic predicates beyond literal arrays.
Mental model
How to reason about binary search
Maintain an interval that is guaranteed to contain every possible answer. Each comparison proves one portion impossible, and every update must make the interval strictly smaller.
Analogy
To find a page in a sorted dictionary, open near the middle and keep only the half whose alphabetical range can still contain the word.
Examples
See the boundary, not just the happy path
Worked example · Exact lookup
lo = 0, hi = n - 1; compare a[mid] with targetSorted order proves whether indices below or above mid can be discarded, giving O(log n) comparisons.
Worked example · First qualifying value
find the first x where feasible(x) is trueWhen feasible is false then permanently true, binary search can locate the transition even without a stored array.
Avoid · Unsorted input
binarySearch([8, 1, 6, 3], 6)A midpoint comparison says nothing about which half contains 6, so discarding a half is not logically valid.
Common mistakes
Misconceptions to remove early
Mixing interval conventions
A closed [lo, hi] interval and a half-open [lo, hi) interval require different loop conditions and updates. Pick one invariant and preserve it.
Failing to shrink past mid
Assigning lo = mid in a closed interval can repeat the same midpoint forever. Use mid + 1 or mid - 1 when mid has been ruled out.
Quick check
Can you predict the result?
1. What property lets binary search discard half of the remaining candidates?
- • An ordering or monotonic predicate that proves one half cannot contain the answer
- • The array has an even number of elements
- • Every value is unique
2. What should be written down before implementing a boundary-style binary search?
Keep building