Binary Search in C++: lower_bound and upper_bound

Binary search finds a value in sorted data by halving the search range each step – about 20 steps for a million elements. The STL gives you three tools – binary_search, lower_bound and upper_bound – and the same halving idea, applied to the answer instead of an array, cracks many hard optimisation problems in contests.

The STL functions

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> v{3, 8, 8, 8, 15, 23, 42};     // must be sorted
    std::cout << std::boolalpha << std::binary_search(v.begin(), v.end(), 15) << ' '
              << std::binary_search(v.begin(), v.end(), 9) << '\n';

    auto lo = std::lower_bound(v.begin(), v.end(), 8);    // first element >= 8
    auto hi = std::upper_bound(v.begin(), v.end(), 8);    // first element > 8
    std::cout << "8 occupies indexes [" << lo - v.begin() << ", " << hi - v.begin() << "), count "
              << hi - lo << '\n';

    auto it = std::lower_bound(v.begin(), v.end(), 20);   // where 20 would be inserted
    std::cout << "first >= 20 is " << *it << " at index " << it - v.begin() << '\n';
    if (std::lower_bound(v.begin(), v.end(), 50) == v.end()) std::cout << "no element >= 50\n";

    int in_range = std::upper_bound(v.begin(), v.end(), 23) - std::lower_bound(v.begin(), v.end(), 8);
    std::cout << in_range << " values in [8, 23]\n";
    return 0;
}

true false
8 occupies indexes [1, 4), count 3
first >= 20 is 23 at index 5
no element >= 50
5 values in [8, 23]

Writing binary search by hand

#include <iostream>
#include <vector>

// first index whose value is >= target (like lower_bound); returns n if none
int first_at_least(const std::vector<int>& a, int target) {
    int lo = 0, hi = static_cast<int>(a.size());   // search in [lo, hi)
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;              // avoids overflow of lo + hi
        if (a[mid] < target) lo = mid + 1;         // answer is to the right of mid
        else hi = mid;                             // mid could be the answer
    }
    return lo;
}

int main() {
    std::vector<int> a{2, 4, 4, 9, 11, 15};
    for (int t : {4, 10, 1, 20}) std::cout << t << " -> index " << first_at_least(a, t) << '\n';
    return 0;
}

4 -> index 1
10 -> index 4
1 -> index 0
20 -> index 6

Using a half-open range [lo, hi) and "find the first position where the condition becomes true" avoids the off-by-one bugs and infinite loops that plague hand-written binary search.

Binary search on the answer

Many problems ask for the minimum (or maximum) value that satisfies a condition, where the condition is monotonic: if X works, every larger X works too. Then you can binary-search over possible answers and test each with a quick check.

#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>

// Split books (pages) among k students in order; minimise the maximum pages any student reads.
bool can_split(const std::vector<int>& pages, int k, long long limit) {
    int students = 1;
    long long current = 0;
    for (int p : pages) {
        if (p > limit) return false;
        if (current + p > limit) { students++; current = 0; }
        current += p;
    }
    return students <= k;
}

int main() {
    std::vector<int> pages{12, 34, 67, 90};
    int k = 2;
    long long lo = *std::max_element(pages.begin(), pages.end());
    long long hi = std::accumulate(pages.begin(), pages.end(), 0LL);
    while (lo < hi) {                                  // first limit for which can_split is true
        long long mid = lo + (hi - lo) / 2;
        if (can_split(pages, k, mid)) hi = mid;
        else lo = mid + 1;
    }
    std::cout << "minimum possible maximum: " << lo << " pages\n";
    return 0;
}

minimum possible maximum: 113 pages

Practice

Summary

Interview practice: sorting and searching questions.