Lesson 11.2 · Binary Search

Lower Bound, Upper Bound and One Reliable Template

Most binary-search bugs come from boundaries. The "first index where a condition is true" template handles first/last positions, insert positions and answers.

15 min

Think of it like this

A row of houses where all the red ones come first and then all the blue ones. You only need to find the first blue house. Every question about sorted data can be phrased as finding that boundary.

1.Find the first true

Define a condition that is false for a prefix and true for the rest, for example nums[i] >= target. Search with lo = 0, hi = n (one past the end, meaning "none"), loop while (lo < hi): if the condition holds at mid, the answer is mid or to its left (hi = mid); otherwise it's to the right (lo = mid + 1). When they meet, lo is the first true index.

With nums[i] >= target this is the lower bound (first position where target could be inserted); with nums[i] > target it's the upper bound (one past the last copy of target).

Bounds.java

public class Main {
    static int lowerBound(int[] a, int t) {       // first index with a[i] >= t
        int lo = 0, hi = a.length;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (a[mid] >= t) hi = mid; else lo = mid + 1;
        }
        return lo;
    }
    static int upperBound(int[] a, int t) {       // first index with a[i] > t
        int lo = 0, hi = a.length;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (a[mid] > t) hi = mid; else lo = mid + 1;
        }
        return lo;
    }
    public static void main(String[] args) {
        int[] a = {1, 3, 3, 3, 5};
        System.out.println(lowerBound(a, 3) + " " + upperBound(a, 3));   // 3s occupy [1, 4)
        System.out.println("count of 3 = " + (upperBound(a, 3) - lowerBound(a, 3)));
        System.out.println("insert 4 at " + lowerBound(a, 4));
    }
}

Output

1 4
count of 3 = 3
insert 4 at 4

▶ Dry run: Lower bound of 3nums = [1, 3, 3, 3, 5], condition nums[i] >= 3

↑lo

↑mid

Step 1/4lo = 0, hi = 5. mid = 2: true, so the first true is at 2 or left of it: hi = 2.

Quick check

Why does the template use hi = mid and lo < hi, not hi = mid − 1 and lo <= hi?

Remember

Phrase the question as "first index where condition is true".
lo = 0, hi = n, while (lo < hi): true → hi = mid, false → lo = mid + 1.
Lower bound uses >=, upper bound uses >.

Common mistakes

Mixing templates (lo <= hi with hi = mid loops forever).
Forgetting that the answer can be n (no element satisfies the condition).

Command Palette

Lower Bound, Upper Bound and One Reliable Template

1.Find the first true