Binary search

Binary search finds a boundary in a sorted range in O(log n) comparisons. The idea is easy; getting the bounds right every time is the skill. The trick that makes it reliable is to stop thinking "find the element" and start thinking "find the first position where a condition becomes true", guarded by a loop invariant you can state in one sentence.

1. The question binary search really answers

Take a sorted sequence and a predicate that is false for a prefix and true for the rest:

Every binary search is "find the first true" for some monotone predicate:

If the predicate is never true, the answer is "one past the end". That's not an error case — it's the natural answer, and it's where you'd insert x.

2. Half-open ranges and the invariant

Keep a candidate range [lo, hi) — lo included, hi excluded — with this invariant:

everything before lo is false; everything from hi on is true.

Initially lo = 0, hi = n: nothing is known, and the invariant holds vacuously. Each step looks at the middle and shrinks the unknown range while keeping the invariant:

#include <cstddef>
#include <print>
#include <span>
#include <vector>

// First index i with v[i] >= target, or v.size() if there is none.
std::size_t lower_bound_index(std::span<const int> v, int target) {
    std::size_t lo = 0, hi = v.size();          // unknown region is [lo, hi)
    while (lo < hi) {                           // non-empty unknown region
        std::size_t mid = lo + (hi - lo) / 2;   // lo <= mid < hi, so v[mid] is valid
        if (v[mid] < target)
            lo = mid + 1;                       // v[mid] is false: everything up to mid is false
        else
            hi = mid;                           // v[mid] is true: mid could be the answer, keep it
    }
    return lo;                                  // lo == hi: the boundary
}

int main() {
    std::vector<int> v{1, 3, 3, 5, 8, 8, 9};
    for (int x : {0, 3, 4, 9, 10})
        std::println("lower_bound({}) = {}", x, lower_bound_index(v, x));
}

Check each line against the invariant:

• mid is always a valid index: lo <= mid < hi <= n because hi - lo >= 1 and integer division rounds down.
• lo = mid + 1 when v[mid] is false: mid and everything before it are false, so they leave the unknown region.
• hi = mid (not mid - 1!) when v[mid] is true: mid might be the first true, so it must stay at the boundary, which hi represents.
• Termination: each step strictly shrinks hi - lo, because mid + 1 > lo and mid < hi.
• Result: when lo == hi the unknown region is empty; by the invariant, lo is the first true.

You never need special cases for empty input, "not found", or one element. If you find yourself writing them, the invariant is probably muddled.

3. mid without overflow

(lo + hi) / 2 overflows when lo + hi exceeds the type's range. With std::size_t that wraps silently (wrong answer); with a signed type it's undefined behaviour.

For indices (0 <= lo <= hi), lo + (hi - lo) / 2 is safe: hi - lo fits whenever hi does. For arbitrary signed ranges it isn't — with lo = INT64_MIN, hi = 0, hi - lo is 2⁶³, one more than INT64_MAX. C++20's std::midpoint(a, b) from <numeric> is exact for the whole range of any integer type (and for pointers), rounding towards a.

#include <climits>
#include <numeric>
#include <print>

int main() {
    int lo = INT_MAX - 10, hi = INT_MAX;
    std::println("{}", lo + (hi - lo) / 2);     // fine: hi - lo is small
    std::println("{}", std::midpoint(lo, hi));  // fine; rounds towards lo
    // (lo + hi) / 2 would be signed overflow: undefined behaviour.

    int a = INT_MIN, b = 0;
    std::println("{}", std::midpoint(a, b));    // fine
    // a + (b - a) / 2 would overflow: b - a is INT_MAX + 1.
}

4. Upper bound: same loop, different predicate

upper_bound is the first element strictly greater than x. Only the comparison changes: an element equal to x is now on the false side.

if (v[mid] <= target) lo = mid + 1;   // "<=": equal elements are false too
else                  hi = mid;

Together they give you equal ranges: all copies of x are in [lower_bound(x), upper_bound(x)), and their count is the difference.

5. Worked example: binary search on the answer

You don't need an array. Any monotone predicate over integers works. What is the smallest k with k * k >= n? The predicate k * k >= n is false, then true, as k grows. Search k in [0, n + 1):

#include <cstdint>
#include <numeric>
#include <print>

// Smallest k in [lo, hi) with pred(k), or hi if none. pred must be monotone.
template <class Pred>
std::int64_t first_true(std::int64_t lo, std::int64_t hi, Pred pred) {
    while (lo < hi) {
        std::int64_t mid = std::midpoint(lo, hi);   // safe for any lo, hi
        if (pred(mid)) hi = mid;
        else           lo = mid + 1;
    }
    return lo;
}

int main() {
    std::int64_t n = 1'000'000'007;
    // k >= ceil(n / k) means k * k >= n, without computing k * k (which could overflow).
    auto ceil_sqrt = first_true(0, n + 1, [&](std::int64_t k) { return k > 0 && k >= (n + k - 1) / k; });
    std::println("ceil(sqrt({})) = {}", n, ceil_sqrt);
}

Faded example — your turn

Fill in the predicate: the smallest number of days d such that working rate units per day finishes work units. (Hint: what must be true of d * rate?) Then answer: what range should you search, and why is the predicate monotone?

auto days = first_true(0, work + 1, [&](std::int64_t d) { return /* ??? */; });

6. The standard library

Prefer the library in real code — it's correct, generic, and works with projections:

#include <algorithm>
#include <print>
#include <string>
#include <vector>

struct Employee {
    std::string name;
    int id;
};

int main() {
    std::vector<int> v{1, 3, 3, 5, 8, 8, 9};
    auto lo = std::ranges::lower_bound(v, 3);
    auto hi = std::ranges::upper_bound(v, 3);
    std::println("3 appears {} times, starting at index {}", hi - lo, lo - v.begin());
    std::println("contains 4? {}", std::ranges::binary_search(v, 4));

    // Projections: search a vector of structs sorted by id, by id.
    std::vector<Employee> staff{{"ana", 10}, {"bo", 20}, {"cy", 30}};
    auto it = std::ranges::lower_bound(staff, 20, {}, &Employee::id);
    std::println("id 20 is {}", it->name);
}

The precondition is that the range is partitioned with respect to the predicate (sorted is the common sufficient case). If it isn't, the result is meaningless — and nothing will tell you. That's a classic bug: searching a vector that was sorted by a different key.

7. Complexity

Each step halves the unknown region, so a search takes ⌈log₂(n + 1)⌉ steps: about 20 for a million elements, 30 for a billion. Contrast that with a linear scan's n/2 average. This is why "sorted + binary search" is often better than a hash table for read-mostly data: no hashing, no extra memory, cache-friendly for small n, and it answers range questions (lower_bound) that hashing can't.

Summary

• Phrase every search as first true of a monotone predicate.
• Use [lo, hi) with the invariant before lo false, from hi true.
• lo = mid + 1 on false, hi = mid on true, loop while (lo < hi), return lo.
• Compute mid as lo + (hi - lo) / 2 for indices; std::midpoint for arbitrary integers.
• In production, use std::ranges::lower_bound / upper_bound / equal_range.