Binary search

Ordered ranges, monotone conditions and boundaries

For a non-descending array, the condition a[i]≥x exhibits "false first, true later", so the boundary between false and true can be found.

Use the half-open interval [l,r), with initial l=0, r=n. Take mid=l+(r−l)/2; if a[mid]≥x, then set r=mid, otherwise set l=mid+1. At the end l=r, which is the first position not less than x, and may equal n.

Each round the interval shrinks, so the query time is O(log n). When finding "whether it exists", you must also confirm that the position is less than n and the corresponding value equals x. upper_bound instead finds the first position strictly greater than x, and subtracting the two gives the number of elements equal to x.

Why binary search takes O(log n) time

Imagine range lengths 16→8→4→2→1: each decision eliminates about half. After k halvings, the size is roughly n/2ᵏ; setting it near 1 gives k≈log₂n. Exact iteration counts depend on midpoint and boundary conventions.

The array-based lower_bound here searches [l, r) for the first element not less than the target. Equality still narrows the range to the left. Unlike a search that returns immediately on equality, this boundary search must finish narrowing. If no element qualifies it returns n; check before accessing a[n]. An early-return search can have O(1) best time and O(log n) worst time. For a nonempty array, this lower_bound implementation makes Θ(log(n+1)) comparisons and uses O(1) auxiliary space.

Lower bound and duplicate counts

Example 1: Handwritten lower_bound

#include <iostream>
#include <vector>
using namespace std;
int lower(const vector<int>& a, int x) {
    int l = 0, r = a.size();
    while (l < r) {
        int m = l + (r - l) / 2;
        if (a[m] >= x) r = m; else l = m + 1;
    }
    return l;
}
int main() {
    vector<int> a = {1, 3, 3, 8};
    cout << lower(a, 3) << " " << lower(a, 9) << endl;
}

Output 1 4. The first occurrence of 3 is at index 1, and the insertion position of 9 is 4 at the end; a[4] cannot be accessed.

Example 2: Two boundaries count duplicate values

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
    vector<int> a = {1, 3, 3, 3, 8};
    cout << upper_bound(a.begin(), a.end(), 3) - lower_bound(a.begin(), a.end(), 3) << endl;
}

Output 3. The first position greater than 3 minus the first position not less than 3 is exactly the length of the duplicate segment.

Tips

• The premise of binary search is that the array is sorted or the condition is monotonic; it cannot be used directly on an unsorted array.
• Finding a candidate position does not mean the target has been found; you must further check the boundary and equality.
• Do not mix the closed-interval r=mid−1 with the half-open-interval r=mid used in this example.

Prerequisites

• Array index

Technical references

• C++ working draft: binary search

Scope note

This lesson is written by InfoCode and is not an official syllabus; the reference level is a site mapping and does not represent official levels, certification or eligibility. Practice records do not establish mastery or eligibility.

Reference level: GESP Level 5 (site mapping)

See contest pathways