Lower and Upper Bound

Binary Search templates for duplicate ranges and insertion positions

Search for a boundary, not an exact match

lower_bound returns the first position whose value is at least the target. upper_bound returns the first position whose value is greater. Their half-open range [lo, hi) allows hi = n, so insertion after the final value needs no special case.

One comparison changes the meaning

Lower bound moves right while a[mid] < target. Upper bound also moves right on equality, using a[mid] <= target. The player runs both searches over the same duplicate-heavy array, then highlights the equal range [lower, upper).

lower_bound: start with half-open range [0, 10) (hi=n sentinel) for target 2.

1function lowerBound(a: number[], t: number): number {
2  let lo = 0, hi = a.length;      // half-open range [lo, hi)，hi=n sentinel
3  while (lo < hi) {
4    const mid = (lo + hi) >> 1;   // probe
5    if (a[mid] < t) lo = mid + 1; // too small: answer is on the right
6    else hi = mid;                // >= t: mid may be the answer
7  }
8  return lo;                      // meeting point = first value >= t
9}
10// upperBound: replace < with <=, so equality also moves right; first value > t
11// count = upperBound - lowerBound

target2

Phaselower_bound

[lo, hi)[0, 10) (hi=n sentinel)

mid—

1 / 14

Reliable library semantics

Each boundary takes O(log n) time and O(1) space. If the target is absent, lower and upper meet at the same insertion position and the count is zero. This is the behavior behind C++ lower_bound, Python bisect, and equivalent standard-library APIs.

Invariant: indices before lo are known to fail the boundary predicate, while indices at or after hi are known to satisfy it.

Review exact-match behavior first in Binary Search.

Algorithm Visualizer

Lower and Upper Bound

Search for a boundary, not an exact match

One comparison changes the meaning

Reliable library semantics