Binary Search

The Invariant

Reframe all binary search problems as returning the index of the first true in a monotone Boolean sequence. The conventions:

• Always represent the unresolved search interval as [lo, hi).
  • Everything before lo is known false.
  • hi is a known or conceptual true boundary.
  • The initial hi may be a past-the-end sentinel; the search never evaluates the predicate at that sentinel.
• The true part is at the end of the sequence: [F, F, T, T, T].
• We search for the first occurrence of true, or return the initial hi if none exists.

This is the template to memorize:

#include <functional>
int binary_search(int lo, int hi, const std::function<bool(int)> &pred)
{
    while (lo < hi) {
        const int mid = lo + (hi - lo) / 2;
        if (pred(mid)) {
            hi = mid;
        } else {
            lo = mid + 1;
        }
    }
    return hi;
}

The Variants

Lower Bound

In an ascending sorted range, search for the first element not smaller than the target.

#include <span>
int lower_bound(std::span<const int> v, int target)
{
    return binary_search(0, v.size(), [&](int i){ return v[i] >= target; });
}

Upper Bound

In an ascending sorted range, search for the first element greater than the target.

#include <span>
int upper_bound(std::span<const int> v, int target)
{
    return binary_search(0, v.size(), [&](int i){ return v[i] > target; });
}

Exact Value Search

Run lower bound first, then compare the found element with the target.

#include <span>
bool contains(std::span<const int> v, int target)
{
    auto i = lower_bound(v, target);
    if (i == v.size()) return false;
    return v[i] == target;
}

Search for the Last True

We may need to search for the last T in an array of the form [T, T, T, F, F]. We can invert the predicate and return the search result - 1. That is, evaluate the array as [F, F, F, T, T], then search for the first T and return its index - 1.

int binary_search_last(int lo, int hi, const std::function<bool(int)> &pred)
{
    int i = binary_search(lo, hi, [&](int i){ return !pred(i); });
    if (i == lo)
        return hi;
    return i - 1;
}

Note: the check i == lo can be omitted if returning lo - 1 on not found is acceptable.

Rotated Array Split Point

The array is rotated: [5, 6, 7, 1, 2, 3, 4]. Spot the monotone pattern: elements in the second sorted segment all <= the last element. (Note: this breaks if the array contains duplicate elements.) The following code returns the index of the beginning of the second sorted segment.

#include <span>
int rotated_split_point(std::span<const int> v)
{
    if (v.empty())
        return 0;
    auto last = v[v.size() - 1];
    return binary_search(0, v.size(), [&](int i){ return v[i] <= last; });
}

Search in Rotated Array

Find the split point, determine which sorted segment contains the answer, and perform binary search on that segment. The predicate must be monotone within each sorted segment. The non-rotated case needs special handling. In our rotated_split_point implementation, a non-rotated array returns the split point at index 0.

#include <span>
int binary_search_rotated(std::span<const int> v, const std::function<bool(int)> &pred)
{
    if (v.empty())
        return 0;

    auto split = rotated_split_point(v);
    if (split == 0 || pred(v.size() - 1))
        return binary_search(split, v.size(), pred);
    else
        return binary_search(0, split, pred);
}