Looking up a word in a physical dictionary does not require flipping through every page. You open it near the middle, check whether the word comes before or after that page, and repeat in the relevant half. Within seconds, thousands of pages narrow down to one.

This idea of repeatedly halving the search space is the essence of binary search. It appears across computer science, from database indexing to machine learning algorithms.

The concept itself is straightforward. The harder parts are recognizing when to apply it and handling the edge cases correctly. Off-by-one errors are easy to introduce. The templates in this chapter cover the standard variants. Problems like rotated-array search, peak finding, and 2D matrix search build on these but need their own invariants.

Binary search is a search algorithm that finds the position of a target value within a sorted collection. Instead of checking each element one by one, it compares the target with the middle element and eliminates half of the remaining elements with each comparison.

The key requirement is that the search space must have a monotonic property. In the simplest case, this means the array is sorted. But more generally, it means there is some condition that is false for all elements on one side of a boundary and true for all elements on the other side.

Why O(log n)?

With each comparison, binary search eliminates half the remaining elements. If you start with n elements:

We stop when only 1 element remains: n/2^k = 1, which gives k = log₂(n).

For an array of 1 billion elements, binary search needs at most 30 comparisons. Linear search might need 1 billion.

The <= vs < choice in the loop condition is not arbitrary. It follows from the interval convention you pick. Two canonical conventions cover every variant in this chapter.

1. Closed-interval search [lo, hi]

The interval includes both endpoints. The invariant is: the target, if present, lies in [lo, hi].

This is the convention used in Variant 1, where every element is checked exactly once before the loop ends.

2. Half-open interval [lo, hi)

The interval includes lo but excludes hi. The invariant is: the first index where the predicate becomes true lies in [lo, hi]. Here hi is treated as a sentinel meaning "past the end of the candidates," so it is a valid answer position even though it is not a valid array index when it equals nums.length.

This is the convention used in Variants 2 through 6, where the goal is to find a boundary rather than an exact element.

Why the +1 in lo = mid + 1 matters

The predicate has already been evaluated at mid. If the predicate is false at mid, then mid cannot be the answer, so the search continues at mid + 1. Without the +1, the loop can stall when hi - lo == 1: at that point mid == lo, and setting lo = mid leaves the interval unchanged, producing an infinite loop.

The upper-bisect rounding rule

When the update is lo = mid instead of lo = mid + 1 (this happens when searching for the rightmost index where a predicate is true), compute mid as lo + (hi - lo + 1) / 2 to round up. With the standard lo + (hi - lo) / 2 formula and hi - lo == 1, mid == lo, so lo = mid again leaves the interval unchanged. Rounding up forces mid == hi, which makes progress.

Binary search is the right tool when your problem has these characteristics:

1. The search space is sorted or has a monotonic property

The classic case is a sorted array. But the search space could also be a range of possible answers where you can determine if an answer is "too small" or "too big."

2. You can eliminate half the search space with each check

Given any point in the search space, you must be able to determine which half contains the answer. This is what makes binary search work.

3. Random access is available

Binary search needs O(1) random access to be O(log n). On a linked list it degrades to O(n log n) because finding the middle element requires walking from the head.

Common problem types where binary search applies:

Binary search has several variants. The core idea is the same, but small changes in the template let you solve different problems. Each variant below comes with a reusable template.

Variant 1: Standard Binary Search (Find Exact Target)

This is the classic version. Given a sorted array, find if a target exists and return its index.

Template:

Key Points:

Example Walkthrough:

Variant 2: Find Lower Bound (First Occurrence)

When duplicates exist, standard binary search might return any occurrence. This variant finds the first (leftmost) occurrence of the target.

Template:

Key Points:

Example Walkthrough:

Variant 3: Find Upper Bound (Last Occurrence)

This variant finds the last (rightmost) occurrence of the target.

Template:

Key Points:

Example Walkthrough:

Variant 4: Find First Element Greater Than Target

Sometimes you need the first element strictly greater than a given value. This is useful for insertion points and range queries.

Template:

Example Walkthrough:

Variant 5: Find First Element Greater Than or Equal To Target

This is equivalent to finding the insertion point if you were to insert the target while maintaining sorted order.

Template:

The loop structure is the same as the find first occurrence template, but the return contract differs: Variant 2 returns -1 when the target is not found, while Variant 5 returns the insertion index.

Variant 6: Binary Search on Answer Space

Instead of searching in an array, this variant searches a range of possible answers. It relies on the property that if a certain value works as an answer, then all values more lenient than it also work.

Template:

Key Points:

Example: Minimum Capacity to Ship Packages

Given packages with weights and a required number of days, find the minimum ship capacity needed.

Variant 6 above shows the template, but the pattern deserves a closer look because it is the most common way binary search appears in mid-to-hard interview problems. The setup is different from searching in an array. Instead of asking "where is element X," the problem asks "what is the smallest or largest value such that some feasibility condition holds." The search space is the range of possible answers, not an array.

Classic examples of this pattern:

The pattern applies when the feasibility predicate is monotonic. If value v is feasible, then every value larger than v is also feasible (or every value smaller, depending on direction). That monotonicity is what makes binary search valid: the feasible values form a contiguous suffix (or prefix) of the candidate range, and you are looking for the boundary.

Template:

Worked example: Koko Eating Bananas.

Koko has piles of bananas, given as an array piles. She picks an eating speed k bananas per hour. Each hour she eats from one pile. If a pile has fewer than k bananas left, she finishes it and moves on; she does not start another pile in the same hour. Given H hours, find the minimum k such that she can finish all piles within H hours.

The feasibility predicate is canFinish(k): returns true if eating at rate k lets her finish in H hours or fewer. The time to finish one pile of size p at rate k is ceil(p / k). The total time is the sum across all piles.

Search bounds:

Monotonicity: if k works, any k' > k also works. Eating faster never takes longer.

Picking the search bounds. This is the part that trips people up most. Two rules cover most problems:

Loose bounds are fine. Binary search is logarithmic, so even a search range of 10^9 finishes in about 30 iterations. The bounds just need to bracket the true answer.

Here is a quick reference for choosing the correct variant:

Here is a problem that combines multiple variants. Given a sorted array with duplicates, count how many elements fall within a range [lo, hi].

Problem: Given nums = [1, 2, 2, 3, 3, 3, 4, 5], count elements in range [2, 3].

Solution: Find the first element >= 2 and the first element > 3. The count is the difference of their indices.

Mistake 1: Off-by-One Errors in Loop Condition

A frequent source of bugs is mixing up left <= right and left < right.

Mistake 2: Integer Overflow in Mid Calculation

Mistake 3: Infinite Loop from Wrong Update

When using left = mid, use mid = left + (right - left + 1) / 2 (round up) to avoid infinite loops.

Mistake 4: Wrong Initial Bounds

Mistake 5: Not Handling Edge Cases

Always consider:

The templates above cover sorted arrays and answer-space search. Several common interview problems apply binary search to inputs that are not strictly sorted, but still have enough structure to halve the search space. Each of these problems has its own invariant; the templates above need small modifications.