Overview

Binary search finds a target in a sorted array by repeatedly comparing with the middle element and discarding the half that cannot contain it. Thirty comparisons are enough for a billion elements. The idea is simple; the implementation is famously easy to get subtly wrong at the boundaries.

The bigger idea is that binary search works on any monotonic predicate — a yes/no question whose answer switches from "no" to "yes" exactly once. "Can Koko finish all bananas at speed k?" is false for small k and true for large k, so you can binary search on k itself. This "binary search on the answer" pattern solves many optimisation problems that look nothing like searching.

Key concepts

Tick a concept once you can explain it in your own words without notes.

Complexity cheat sheet

OperationCost
Search in sorted arrayO(log n)
Binary search on answerO(log(range) × cost of feasibility check)
Lower/upper boundO(log n)

Patterns to recognise

Exact match

Use it for: Classic search in a sorted array.

Return when a[mid] equals the target; otherwise discard a half.

First true

Use it for: First bad version, lower bound, search insert position.

If ok(mid), record and go left (hi = mid − 1); else go right.

Minimise the maximum

Use it for: Ship packages in D days, split array largest sum, Koko eating bananas.

Binary search the answer value; check feasibility greedily in O(n).

Code template

Reusable "first true" template + Koko eating bananas

Common mistakes

  • Mixing conventions (inclusive hi with <, or lo = mid with an exclusive bound) is the source of most infinite loops.
  • The predicate must be truly monotonic; otherwise binary search returns garbage silently.
  • Test with arrays of size 1 and 2, and with the target at both ends.

Quick check

Three questions on Binary Search. Get all three right to earn +15 XP.

  1. What must be true for binary search to work?

  2. Why write mid = lo + (hi - lo) / 2 instead of (lo + hi) / 2?

  3. "Binary search on the answer" applies when:

Challenges

Ordered from easiest to hardest. Solve them on LeetCode, then tick them off here. Know every concept and solve 3 to clear the level.

Stuck on Binary Search?Ask Orbi for a hint, a fresh explanation or a review of your code.

Ask the tutor