Binary Search

O(log n) on any sorted (or monotonic) space — and the universal template that survives every off-by-one trap.

intermediatePractice Full theoryPrereq:Arrays & Hashing

Start practice Read the theory See all problems

What you'll learn

Recognise sorted OR monotonic-predicate problems as binary-search candidates
Write the universal 'first true' template without off-by-one bugs
Compute mid safely to avoid integer overflow
Find lower/upper bounds (first/last occurrence) of a value
Search a rotated sorted array by deciding which half is sorted
Apply 'binary search on the answer' to min/max feasibility problems

When to reach for this

Signals (use it)

Sorted array + 'find / find first / find last / insert position'
"Minimum/maximum value such that <condition> holds" → search on answer
Rotated sorted array search
A monotonic predicate: once true, always true (or vice versa)
O(n) is too slow and the space has order you can exploit

Anti-signals (don't)

Unsorted data with no monotonic property → sort first or hash
You need all matches, not a boundary → linear scan after finding one
Tiny n where O(n) is already trivial

Theory & deep dive

Binary search repeatedly halves the search space, finding an answer in O(log n) instead of O(n). Its real power isn't just searching sorted arrays — it's searching any monotonic space, where a yes/no condition flips exactly once from false to true. That insight ("binary search on the answer") turns many hard optimisation problems into easy ones.

The reason binary search has a reputation for being tricky is the off-by-one minefield: lo <= hi vs lo < hi, mid+1 vs mid, infinite loops. The cure is to stop memorising five variants and instead learn one template built around the question "find the first index where a condition becomes true". Every variant — exact match, lower bound, rotated array, search-on-answer — is that one template with a different condition.

This module gives you that universal template, the monotonic-predicate mental model, and the rotated-array and search-on-answer variants.

The big idea in plain words

Binary search is the 'guess my number between 1 and 100' game played perfectly. You guess 50; if you're told 'higher', you instantly forget 1 through 50 and only think about 51 through 100. Every guess throws away half of what's left, so even a million numbers take only about 20 guesses.

Example: find 7 in [1, 3, 5, 7, 9]. The middle value is 5, which is smaller than 7, so ignore the whole left half. The middle of what remains is 7 - found in just two checks instead of scanning all five. The catch: this only works when the data is sorted (or otherwise ordered), because that order is what lets you trust 'go this way'.

The mental model: monotonic predicates

Forget 'sorted array' for a moment. Binary search works on any boolean predicate f(x) that is monotonic: false, false, ..., false, true, true, ..., true. Binary search finds the boundary — the first x where f(x) is true.

Concept	Meaning
Search space	The range `[lo, hi]` of candidate answers
Predicate f(x)	A yes/no test that flips exactly once
Boundary	The first x where f(x) becomes true — the answer
Invariant	f(lo-1) is false, f(hi+1) is true (the answer is in [lo,hi])

Searching a sorted array for target is just the predicate f(i) = (arr[i] >= target). Reframing every problem as 'find the boundary of a monotonic predicate' is what makes the off-by-ones disappear.

The universal template

Use the half-open [lo, hi) form. It converges to the first index where the condition holds, and it can't infinite-loop because the range strictly shrinks every iteration.

Java· Universal 'first true' template

// Returns first index in [0,n] where condition(i) is true.
int binarySearch(int n) {
    int lo = 0, hi = n;            // half-open [lo, hi)
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;   // overflow-safe
        if (condition(mid)) hi = mid;   // answer is mid or left
        else                lo = mid + 1; // answer is strictly right
    }
    return lo;   // == hi: the boundary
}

Tip

Compute mid as lo + (hi - lo) / 2, not (lo + hi) / 2, in Java/C++ to avoid integer overflow when lo and hi are large. Python ints are unbounded so it doesn't matter there.

Exact match, lower bound, upper bound

All three are the universal template with a different predicate.

Goal	Predicate condition(mid)	After loop
First index ≥ target (lower bound)	`arr[mid] >= target`	`lo` is insertion point
First index > target (upper bound)	`arr[mid] > target`	`lo` is past last match
Exact match	lower bound, then check `arr[lo] == target`	found / not found
Count of target	`upperBound - lowerBound`	the count

This is why you only need one template: change the comparison, get a different boundary. First-and-last-position problems are just lower bound and upper bound back to back.

Searching a rotated sorted array

A rotated sorted array (e.g. [4,5,6,7,0,1,2]) isn't globally sorted, but at any mid, one half is always sorted. Detect which half is sorted by comparing arr[lo] to arr[mid]; if target lies within that sorted half's range, search it, otherwise search the other half. Still O(log n).

Python· Search in rotated sorted array

def search_rotated(a, target):
    lo, hi = 0, len(a) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if a[mid] == target:
            return mid
        if a[lo] <= a[mid]:              # left half sorted
            if a[lo] <= target < a[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:                            # right half sorted
            if a[mid] < target <= a[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1

Binary search on the answer

The advanced superpower. When a problem asks for the minimum (or maximum) value such that some condition is feasible, and feasibility is monotonic in that value, binary-search the answer itself.

Examples: 'minimum eating speed to finish bananas in h hours' (Koko), 'smallest divisor given a threshold', 'capacity to ship packages in d days', 'split array into k parts minimising the largest sum'. The recipe: define feasible(x) (can we do it with value x?), confirm it's monotonic, then binary search the smallest feasible x.

Note

The search space here is the range of possible answers (e.g. 1..maxValue), not array indices. The 'array' is conceptual — you evaluate feasible(mid) instead of reading arr[mid].

How to talk about this in the interview

“Frame it as a boundary search: "The array is sorted, so I can binary search in O(log n). I'll look for the first index where arr[i] >= target using the half-open template, which avoids off-by-one bugs." For optimisation problems, say the magic words: "The feasibility is monotonic — if speed x works, any larger speed works — so I'll binary search on the answer instead of the array." Always mention overflow-safe mid and state O(log n) time, O(1) space.”

Common mistakes

–Computing mid as (lo + hi) / 2 and overflowing in Java/C++ — use lo + (hi - lo) / 2
–Mixing `lo <= hi` (closed) with `hi = mid` (half-open) updates → infinite loop
–Updating `lo = mid` instead of `lo = mid + 1`, never shrinking the range
–Binary-searching data that isn't sorted or monotonic
–In rotated search, comparing to the wrong endpoint to decide which half is sorted
–Forgetting to verify arr[lo] == target after a lower-bound search

Complexity summary

Binary search is O(log n) time and O(1) space (iterative). 'Binary search on the answer' is O(log(range) × cost-of-feasibility-check); if each feasibility check is O(n), the total is O(n log(range)).

Practice problems

16 total

Binary Search