Binary Search Variations: Lower Bound, Upper Bound & Boundaries

Plain binary search answers “is x here?”. But real problems ask sharper questions: where does x first appear?, how many copies are there?, what’s the smallest element ≥ x? These are all answered by boundary binary search — searching for the dividing line in a sorted array rather than an exact value. The key tools are lower_bound and upper_bound.

The two boundaries

Think of a sorted array split by a value x:

lower_bound(x) = the first index whose element is ≥ x. (The leftmost spot x could be inserted while keeping order.)
upper_bound(x) = the first index whose element is > x. (The rightmost insertion spot.)

From these two everything else falls out:

First occurrence of x = lower_bound(x) (if that element actually equals x).
Last occurrence of x = upper_bound(x) - 1.
Count of x = upper_bound(x) - lower_bound(x).

The half-open template

These variations are cleanest with a half-open range [lo, hi) and the condition lo < hi. We never break early on equality — we keep shrinking until lo lands exactly on the boundary.

// first index with a[i] >= target  (==a.size() if none)
int lowerBound(const std::vector<int>& a, int target) {
    int lo = 0, hi = (int)a.size();           // half-open [lo, hi)
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] < target) lo = mid + 1;    // mid too small, go right
        else hi = mid;                         // mid is a candidate, keep it
    }
    return lo;
}
// first index with a[i] > target
int upperBound(const std::vector<int>& a, int target) {
    int lo = 0, hi = (int)a.size();
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] <= target) lo = mid + 1;
        else hi = mid;
    }
    return lo;
}

// first index with a[i] >= target  (==a.length if none)
int lowerBound(int[] a, int target) {
    int lo = 0, hi = a.length;                 // half-open [lo, hi)
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] < target) lo = mid + 1;     // mid too small, go right
        else hi = mid;                          // mid is a candidate, keep it
    }
    return lo;
}
// first index with a[i] > target
int upperBound(int[] a, int target) {
    int lo = 0, hi = a.length;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] <= target) lo = mid + 1;
        else hi = mid;
    }
    return lo;
}

// first index with a[i] >= target  (==a.length if none)
function lowerBound(a, target) {
  let lo = 0, hi = a.length;                 // half-open [lo, hi)
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (a[mid] < target) lo = mid + 1;       // mid too small, go right
    else hi = mid;                            // mid is a candidate, keep it
  }
  return lo;
}
// first index with a[i] > target
function upperBound(a, target) {
  let lo = 0, hi = a.length;
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (a[mid] <= target) lo = mid + 1;
    else hi = mid;
  }
  return lo;
}

# first index with a[i] >= target  (== len(a) if none)
def lower_bound(a, target):
    lo, hi = 0, len(a)                    # half-open [lo, hi)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if a[mid] < target:
            lo = mid + 1                  # mid too small, go right
        else:
            hi = mid                      # mid is a candidate, keep it
    return lo

# first index with a[i] > target
def upper_bound(a, target):
    lo, hi = 0, len(a)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if a[mid] <= target:
            lo = mid + 1
        else:
            hi = mid
    return lo

For beginners: “Half-open [lo, hi)” means lo is included but hi is not. That’s why hi starts at n (one past the last index) and why we write hi = mid (not mid - 1) — mid stays a live candidate.

First and last occurrence

With the two bounds in hand, locating the exact span of a value with duplicates is trivial. For an array like [1, 2, 2, 2, 5] and target 2:

// returns {first, last} indices of target, or {-1, -1} if absent
std::pair<int,int> firstAndLast(const std::vector<int>& a, int target) {
    int lo = lowerBound(a, target);
    if (lo == (int)a.size() || a[lo] != target) return {-1, -1};
    int hi = upperBound(a, target) - 1;
    return {lo, hi};
}

// returns [first, last] indices of target, or [-1, -1] if absent
int[] firstAndLast(int[] a, int target) {
    int lo = lowerBound(a, target);
    if (lo == a.length || a[lo] != target) return new int[]{-1, -1};
    int hi = upperBound(a, target) - 1;
    return new int[]{lo, hi};
}

// returns [first, last] indices of target, or [-1, -1] if absent
function firstAndLast(a, target) {
  const lo = lowerBound(a, target);
  if (lo === a.length || a[lo] !== target) return [-1, -1];
  const hi = upperBound(a, target) - 1;
  return [lo, hi];
}

# returns (first, last) indices of target, or (-1, -1) if absent
def first_and_last(a, target):
    lo = lower_bound(a, target)
    if lo == len(a) or a[lo] != target:
        return (-1, -1)
    hi = upper_bound(a, target) - 1
    return (lo, hi)

Complexity

Every variation is O(log n) time and O(1) space — the same halving as plain binary search; only the comparison changes.

Built-ins worth knowing

You rarely write these from scratch in production — but you must understand them to use them right:

C++: std::lower_bound, std::upper_bound, std::equal_range.
Java: Arrays.binarySearch (note: returns an index for duplicates, not necessarily the first).
Python: bisect.bisect_left (= lower bound), bisect.bisect_right (= upper bound).
JavaScript: no built-in — the templates above are the standard.

Pitfall: Mixing range styles is the #1 source of bugs. The plain-search template uses inclusive [lo, hi] with lo <= hi and hi = mid - 1; the boundary template here uses half-open [lo, hi) with lo < hi and hi = mid. Pick one style per function and keep mid updates consistent with it.

Going deeper: The boundary mindset — “find the dividing line where a condition flips from false to true” — generalizes far beyond arrays. That exact idea powers binary search on the answer.

Next: sweep sorted arrays with the two-pointers technique, or try the searching exercises.