Lower Bound, Upper Bound & Element Occurrences

Topics Covered:
51. Binary Search Invariants & Interval Models • 52. Lower Bound Algorithm ($A[i]\ge \text{target}$) • Upper Bound Algorithm ($A[i]>\text{target}$) • 53. First and Last Occurrences & Frequency Counting in $O(\log n)$ • Production Multi-Language Implementations

Beyond locating exact single-element matches, binary search serves as a precision tool for locating boundaries in sorted sequences. Standard binary search halts unpredictably on any arbitrary instance of a duplicate target. In production algorithms, standard libraries (such as C++ std::lower_bound and std::upper_bound, Java Arrays.binarySearch, and Python bisect_left/bisect_right) rely on invariant-preserving predicates to find the exact boundaries of duplicate runs. This chapter formalizes binary search interval models, strict versus non-strict monotonic boundary predicates, candidate-tracking state machines, and $O(\log n)$ frequency range evaluations.

• Differentiate the three fundamental binary search interval paradigms (Closed $[low,high]$, Half-Open $[low,high)$, and Open $(low,high)$).
• Formulate the exact mathematical predicates defining Lower Bound ($A[i]\ge \text{target}$) and Upper Bound ($A[i]>\text{target}$).
• Prove why the total frequency of any element in a sorted array equals $\text{UpperBound}-\text{LowerBound}$ in guaranteed $O(\log n)$ time.
• Implement dedicated FirstOccurrence and LastOccurrence variants using candidate-retention variables and directional interval compression.
• Trace boundary conditions where the search key is strictly smaller than $A[0]$, strictly greater than $A[n-1]$, or present across contiguous duplicate spans.

C++20 Lower Bound, Upper Bound & Range Count

#include <span>
#include <cstddef>
#include <utility>

// Lower Bound: Returns index of first element >= target, or arr.size() if none
size_t lower_bound(std::span<const int> arr, int target) {
    size_t low = 0;
    size_t high = arr.size();

    while (low < high) {
        size_t mid = low + (high - low) / 2;
        if (arr[mid] >= target) {
            high = mid; // Candidate found; continue searching left
        } else {
            low = mid + 1;
        }
    }
    return low;
}

// Upper Bound: Returns index of first element > target, or arr.size() if none
size_t upper_bound(std::span<const int> arr, int target) {
    size_t low = 0;
    size_t high = arr.size();

    while (low < high) {
        size_t mid = low + (high - low) / 2;
        if (arr[mid] > target) {
            high = mid; // Candidate found; continue searching left
        } else {
            low = mid + 1;
        }
    }
    return low;
}

// O(log n) Exact Frequency Query
size_t count_occurrences(std::span<const int> arr, int target) {
    size_t lb = lower_bound(arr, target);
    if (lb == arr.size() || arr[lb] != target) {
        return 0; // Target is absent
    }
    size_t ub = upper_bound(arr, target);
    return ub - lb;
}

Binary search is fundamentally not an algorithm for searching arrays; it is an algorithm for finding the transition boundary of any monotonic boolean predicate over a discrete or continuous domain:

Let $P:\mathbb{Z}\to \{0,1\}$ be a boolean function evaluated over range $[L,R]$. If $P$ is monotonic:

The truth values across the domain decompose into two contiguous partitions:

Binary search locates the unique boundary point $x^{\ast }$ (the smallest $x$ where $P(x)=\text{True}$) in strictly $\lceil {\log }_2(R-L+1)\rceil$ predicate evaluations.

TypeScript Implementation

/**
 * Binary search on monotonic answer space [low, high].
 * Finds the minimal integer x such that predicate(x) is true.
 * Assumes predicate evaluation is monotonic: [F, F, ..., F, T, T, ..., T].
 */
export function searchFirstTrue(
  low: number,
  high: number,
  predicate: (val: number) => boolean
): number {
  let left = low;
  let right = high;
  let ans = high + 1; // Default if no value satisfies predicate

  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);
    if (predicate(mid)) {
      ans = mid;         // Candidate found; try smaller values on left
      right = mid - 1;
    } else {
      left = mid + 1;    // Feasibility fails; must search right
    }
  }

  return ans;
}

Modern C++20 Implementation: Template Predicate Binary Search

#include <concepts>
#include <cstdint>

template <std::integral T, typename Predicate>
requires std::predicate<Predicate, T>
T searchFirstTrue(T low, T high, Predicate pred) {
    T left = low;
    T right = high;
    T ans = high + 1;

    while (left <= right) {
        T mid = left + (right - left) / 2;
        if (pred(mid)) {
            ans = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return ans;
}

1. Predicate Distinction: Lower Bound uses a non-strict inequality ($A[i]\ge \text{target}$); Upper Bound uses a strict inequality ($A[i]>\text{target}$).
2. Fallback Index: If no element satisfies the predicate, both Lower and Upper Bound return $n$ (the valid insertion position preserving sorted order).
3. Range Counting: The exact frequency of any element in a sorted array is computed in $O(\log n)$ time as $\text{UpperBound}-\text{LowerBound}$.
4. Candidate Tracking: Half-open intervals $[low,high)$ guarantee convergence to the optimal boundary point with zero pointer underflow.
5. Universal Predicate Framework: Any monotonic feasibility function $P(x)$ can be inverted via binary search in $O(\log (\text{Range})\cdot T_{\text{predicate}})$ time.

1. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Introduction to Algorithms (4th ed.), Section 2.3 & Chapter 12. MIT Press.
2. Bentley, J. (2000). Programming Pearls (2nd ed.), Column 4: Writing Correct Programs. Addison-Wesley.
3. Stepanov, A., & Lee, M. (1995). The Standard Template Library (STL). HP Laboratories Technical Report HPL-95-11.
4. Knuth, D. E. (1998). The Art of Computer Programming, Volume 3: Sorting and Searching (2nd ed.), Section 6.2. Addison-Wesley.

• VisuAlgo Binary Search: Interactive visualization of interval contraction, lower bound, and upper bound pointer tracking.
• GeeksforGeeks Binary Search Library: Comprehensive compendium of standard library search routines and interval models.

1. LeetCode 34: Find First and Last Position of Element in Sorted Array (Medium) — Direct application of lower bound and upper bound.
2. LeetCode 35: Search Insert Position (Easy) — Canonical lower bound returning the insertion index.
3. LeetCode 875: Koko Eating Bananas (Medium) — Monotonic predicate binary search on rate answer space.
4. LeetCode 410: Split Array Largest Sum (Hard) — Minimax partition search via monotonic greedy validation.
5. LeetCode 33: Search in Rotated Sorted Array (Medium) — Piecewise monotonic binary search with pivot discontinuity invariants.