Pattern Studioalgorithmic thinking
All patterns

Binary Search

Searching
Beginner
Interactive

Discard half the candidates per comparison for O(log n) lookups.

Time
O(log n)
Space
O(1)
ActiveComparingMatch / bestIn windowFrontierVisitedExcludedAnswer
No frames to display.

The idea

Binary search repeatedly probes the middle of a sorted range and uses the ordering to throw away the half that cannot contain the answer. Twenty comparisons suffice to pinpoint one item among a million.

The deeper skill is 'binary search on the answer': whenever a predicate is monotonic (false, false, …, true, true), you can binary-search for the boundary even when there is no literal sorted array — think minimum feasible capacity, earliest valid time, or smallest k that works.

Analogy

Guessing a number between 1 and 100. Each guess of the midpoint and a 'higher / lower' reply halves the range — you home in within seven guesses.

When to reach for it

  • The data (or the answer space) is sorted / monotonic.
  • You need a value, a boundary, or a first/last position.
  • A linear scan is too slow for the input size.

Language-independent template

lo, hi = 0, n - 1
while lo <= hi:
    mid = lo + (hi - lo) // 2
    if check(mid): return mid
    elif tooSmall(mid): lo = mid + 1
    else: hi = mid - 1

Complexity — time O(log n), space O(1).

Common mistakes

  • Computing mid = (lo + hi) / 2 and overflowing — prefer lo + (hi - lo) / 2.
  • Inconsistent bounds causing an infinite loop (mixing inclusive/exclusive hi).
  • Using < vs <= incorrectly for the loop condition.

Practice progression

Canonical interview problems, ordered from foundation to advanced application.

Easy
Binary SearchLC 704

Return a target's index in a sorted array or -1.

Medium
Search in Rotated Sorted ArrayLC 33

Find a target in a rotated array in logarithmic time.

Hard
Median of Two Sorted ArraysLC 4

Find the combined median in logarithmic time.

Variations

Lower / upper bound (first index ≥ / > target).
Rotated sorted array search.
Binary search on the answer (Koko eating bananas, ship-within-days).