The introduction to binary search covered the standard version: find a target in a sorted array, or return -1. That version returns an index where the target appears. Many problems need something more specific, such as the first or last occurrence of a value, the position where a value should be inserted, or the smallest answer that satisfies a condition.

This chapter covers those variations. Each one keeps the same core idea, cutting the search space in half with every comparison, but changes the loop condition, the pointer updates, or what gets returned. The templates below cover the standard variants. Problems like rotated-array search, peak finding, and 2D matrix search build on these but need their own invariants.

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 not limited to finding a value in a sorted array. These are the common problem types where it 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.