Binary Search Boundaries

When the input is sorted (or rotated sorted), think binary search. Each step halves the range, so a search over $n$ items takes $O(\log n)$. Most bugs come from two decisions: the loop condition and what the pointers mean when the loop ends. This note fixes both for exact matches, first and last occurrences, and floor and ceiling.

The idea#

Choose the loop condition by what you are looking for.

Once the condition is set, one rule of thumb decides what the loop body does:

• Exact match: check nums[mid] == target and return.
• Closest or threshold match: don't stop early. Let the pointers cross and read the answer from l and r. This squeezes the range down onto the boundary.

The post-loop sandwich#

Letting the pointers cross only helps if you know where they stop. With l <= r, the loop ends only when l = r + 1. If the target isn't present, the pointers have sandwiched the spot where it would be:

• r sits on the largest value smaller than the target (the floor).
• l sits on the smallest value larger than the target (the ceiling), which is also the insertion index.

This works because of an invariant: everything left of l is smaller than the target, and everything right of r is larger. Each step keeps that true, so when the range is empty, r and l are the two neighbors of the gap.

Record and keep going#

The sandwich handles a missing target. Duplicates need one more idea. For the first occurrence, a hit at mid is only a candidate: there may be an earlier one. Note it down and keep searching left. For the last occurrence, note it and search right.

How to spot it#

These cues point to a boundary search.

• Sorted array plus "first", "last", "insert position", "smallest greater than", "largest at most".
• "Return the index where it would be" or "the closest value".
• A yes/no API that flips once (bad version, guess higher or lower).
• An integer answer to a monotone question, such as the floor of a square root.

Template#

One loop covers the exact match and the first or last occurrence. Pass a find_first flag instead of toggling shared state.

l, r = 0, len(nums) - 1
found = -1
while l <= r:
    mid = (l + r) // 2
    if nums[mid] == target:
        found = mid                  # a candidate, not yet the edge
        if find_first: r = mid - 1   # an earlier copy may exist
        else: l = mid + 1            # a later copy may exist
    elif nums[mid] < target:
        l = mid + 1
    else:
        r = mid - 1
return found

For a plain exact match, drop found and return on a hit instead. After the loop, r is the floor and l is the ceiling. Either can be off the end (-1 or len(nums)).

Pitfalls#

Off-by-one errors here usually come from one of these.

• Mixing loop styles. l <= r goes with r = mid - 1; l < r goes with r = mid. Mixing them loops forever or skips the answer.
• Stopping on the first hit when the question asks for the first or last occurrence.
• Reading l out of range. After the loop, l can equal len(nums) and r can be -1. Guard before indexing.
• Overflow guards. l + (r - l) // 2 matters in fixed-width languages; Python integers don't overflow, so (l + r) // 2 is fine.

Problems in this pattern#

These problems use this pattern. Solve them before you open the hints below. Start with the first two.

• 704. Binary Search
• 35. Search Insert Position
• 278. First Bad Version
• 374. Guess Number Higher or Lower
• 69. Sqrt(x)
• 744. Find Smallest Letter Greater Than Target
• 34. Find First and Last Position of Element in Sorted Array
• 1300. Sum of Mutated Array Closest to Target
• 4. Median of Two Sorted Arrays

Hints#

Open a hint only after you have tried the problem for a while.

Key takeaways#

• l <= r for a specific target; l < r to narrow down to one index.
• Exact match: check mid. Closest or threshold: let the pointers cross.
• After l <= r fails, r is the floor and l is the ceiling (and the insert position).
• For first or last occurrence, record the hit and keep searching in that direction.
• Always guard l == len(nums) and r == -1 before indexing.