The One Template: First True

Binary Search, lesson 2 of 3

The One Template: First True

A single off-by-one-proof loop for lower bound, upper bound and every variation.

13 min, 0 of 4 activities solved

View cheatsheet

Getting Python ready… examples can run in a moment.

Binary search has a reputation for off-by-one bugs: < or <=? mid or mid + 1? len(nums) or len(nums) - 1? The cure is to learn one template and turn every problem into it.

Every search is "find the first index where a predicate is True", for a predicate that looks like F F F ... T T T:

def first_true(lo, hi, pred):
    # answer is in [lo, hi]
    # (hi itself means "no True at all")
    while lo < hi:
        mid = (lo + hi) // 2
        if pred(mid):
            hi = mid       # mid may be it
        else:
            lo = mid + 1   # it's right of mid
    return lo              # lo == hi

The invariant that makes it correct: everything left of lo is False, and everything from hi on is True (or past the end). Each step keeps that true and shrinks the gap. When lo == hi the gap is empty, so lo sits exactly on the boundary.

Why it always stops: (lo + hi) // 2 rounds down, so lo <= mid < hi. Both hi = mid and lo = mid + 1 make the range strictly smaller.

Example

Dry run: first index with nums[i] >= 5

Notice hi starts at len(nums), one past the end. That extra slot is the answer "no index works", and mid never reaches it (mid < hi), so nums[mid] can't go out of range.

Quiz

What does this print?

Lower bound and upper bound. Two predicates cover almost every sorted-array question:

You want Predicate Python
first index with value >= x a[i] >= x bisect_left(a, x)
first index with value > x a[i] > x bisect_right(a, x)
how many x's right - left bisect_right - bisect_left
last index with value <= x first > x, minus 1 bisect_right(a, x) - 1
last index with value < x first >= x, minus 1 bisect_left(a, x) - 1

"Is x present?" is lower bound plus one check after the loop: i < len(a) and a[i] == x.

The same "minus 1" trick handles last True for a T T T F F F predicate: find the first index where it's False, then step back one.

Example

The bisect module does the same

bisect is fine in real code and usually in interviews, but be ready to write the loop: many problems (rotated arrays, "search on the answer") don't have a ready-made list to bisect. insort is O(n) because the list shifts.

Quiz

What does this print?

Quiz

You need the LAST index where nums[i] <= x. Which call gives it?

Exercise

First and last position

nums is sorted (with duplicates). Write search_range(nums, target) returning [first, last]: the first and last index of target, or [-1, -1] if it's missing. It must be O(log n), so write the loop yourself rather than importing bisect.

Trick: last is one before the lower bound of target + 1.