Lower bound and upper bound: the boundary templates

Plain binary search answers "is the target here?" — and with duplicates it returns some matching index. Most real questions ask about a boundary instead: where does the first 3 start? Where do the 3s end? Where would a 4 be inserted? Two small variations of binary search answer all of these: the lower bound and the upper bound.

The idea: find the first yes

Ask the same yes/no question of every index: "is `nums[i] >= target`?" Because the array is sorted, the answers are all no up to some point and all yes after it. The lower bound is the first yes. Binary search finds it: if mid says yes, the first yes is mid or to its left; if no, it's to the right.

The answer can also be n — when every answer is no, "the first yes" is just past the end, which is exactly where the target would be inserted. So the search space is low = 0 to high = n, both possible answers.

How it works

The code: lower bound

1function lowerBound(nums, target) {2  let low = 0;3  let high = nums.length;                  // nums.length means "after everything"4  while (low < high) {5    const mid = low + Math.floor((high - low) / 2);6    if (nums[mid] < target) low = mid + 1;   // mid says no: the first yes is to the right7    else high = mid;                         // mid says yes: it might be the first one, keep it8  }9  return low;                              // the first index with nums[i] >= target10}

Why it always stops. mid is always less than high (the division rounds down), so high = mid shrinks the range, and low = mid + 1 does too. And it's never wrong: high = mid keeps the yes it just saw, and low = mid + 1 only drops no's. O(log n) time, O(1) space.

Upper bound: change one comparison

The upper bound asks "is nums[i] > target?" — the first value strictly bigger. The only change is < becoming <=: a value equal to the target now counts as no.

1function upperBound(nums, target) {2  let low = 0;3  let high = nums.length;4  while (low < high) {5    const mid = low + Math.floor((high - low) / 2);6    if (nums[mid] <= target) low = mid + 1;  // equal still says no7    else high = mid;8  }9  return low;                              // the first index with nums[i] > target10}

What the two bounds answer

lower = lowerBound(nums, t), upper = upperBound(nums, t)

Is t present?               lower < n and nums[lower] == t
First index of t            lower           (if present)
Last index of t             upper - 1       (if present)
How many t's                upper - lower
Where to insert t           lower           (keeps the array sorted)
How many values < t         lower
How many values <= t        upper

Libraries have them built in: Python's bisect_left and bisect_right, C++'s lower_bound and upper_bound. Java's Arrays.binarySearch isn't one — with duplicates it returns any match.

The general template

Nothing above depends on the question being about nums[i]. Any yes/no question that flips once, from no to yes, can be searched the same way. This is the template the rest of the course uses:

low, high = first candidate, last candidate (+1 if "none" is possible)
while low < high:
    mid = low + (high - low) // 2
    if condition(mid):  high = mid        # mid works: the answer is mid or to its left
    else:               low = mid + 1     # mid fails: the answer is to its right
return low                                # the first candidate that works

To find the last no instead, take the first yes and subtract one. Frame every boundary problem as "the first index where …" and the off-by-one bugs disappear.

Key takeaways