C++UCS301
SearchingC++17

Binary Search Patterns

Lower bound, upper bound, answer-space search, and rotated-array search extend binary search beyond exact lookup.

Open this in the visual lab

What to understand

  • First true predicate
  • lower_bound and upper_bound
  • Search on answer
  • Duplicate and boundary handling

Remember this

  1. 1Define the predicate before coding
  2. 2Prove monotonicity
  3. 3Return the saved boundary, not an arbitrary midpoint

Detailed notes

Boundary search locates the transition in a monotone predicate: false values followed by true values. lower_bound is the first position whose value is not less than the target; upper_bound is the first position strictly greater.

Search on answer applies the same idea when no array exists. If a candidate capacity, time, or distance can be tested and feasibility changes monotonically, binary search can find the smallest feasible answer.

How it works

  1. 1Write a boolean predicate for a candidate answer.
  2. 2Prove that the predicate changes at most once.
  3. 3Pick the first-true or last-true template.
  4. 4Return the boundary after convergence and validate impossible cases.

Where it is used

  • First/last occurrence and equal ranges
  • Minimum feasible capacity or maximum valid threshold
  • Rotated arrays and monotone matrix search

Common mistakes

  • Searching a non-monotone predicate
  • Returning immediately on equality when a boundary is required
  • Failing to preserve an answer when searching a closed numeric range

Complexity analysis

OperationBestAverageWorstExtra space
Boundary searchO(log n)O(log n)O(log n)O(1)
Answer-space searchO(log range)O(log range)O(log range)O(1)

C++ implementation

C++17 reference
main.cpp

First element not less than target

This half-open interval pattern returns values.size() when no valid position exists.

int lowerBound(const vector<int>& values, int target) {
    int low = 0, high = static_cast<int>(values.size());
    while (low < high) {
        int mid = low + (high - low) / 2;
        if (values[mid] < target) low = mid + 1;
        else high = mid;
    }
    return low;
}
9 linesUTF-8 · C++ study reference

Exam & viva

Open a prompt when you are ready to check your answer.