Pattern 4 of 18 · Foundations

Binary Search

Halve the search space every step — not just on sorted arrays, but on answer spaces too.

Repeatedly halve the search space by comparing the middle element to a target, turning an O(n) scan into O(log n). It works on more than sorted arrays — any "answer space" that's monotonic (true…true…false…false) can be binary searched.

Key concepts

  • Classic search: find a target's index in a sorted array.
  • Search on rotated arrays: figure out which half is still sorted, then decide which half to discard.
  • Binary search on the answer: instead of searching an array, search a range of possible answers and check "is this answer feasible?"

When to use it

  • The input is sorted, or partially sorted (like a rotated sorted array).
  • You're minimizing or maximizing a value where "is X feasible?" is easy to check and feasibility is monotonic.

Tips

  • Decide your loop invariant up front (is `right` inclusive or exclusive?) — that's where most bugs live.
  • For rotated arrays, compare `nums[mid]` to `nums[left]` to figure out which half is sorted before deciding where to search next.
  • If you're searching "the smallest value that satisfies condition X," you're binary searching on the answer, not the array.

Practice problems (7)

Blind 75 (2):

More from Blind 150 (5):

← StackSliding Window →

See the full roadmap →