Binary Search: Halve a Sorted Row Until One Place Is Left

Amara's bookshop keeps a printed list of its 16 book prices, from the cheapest up. A customer asks whether any book costs exactly 300 taka. Another wants to know where a new 310-taka book would go on the list. Reading the list from the front can take 16 looks for each question. The children's game of "higher or lower" needs at most 5. This lesson is that game, played by the library on a sorted vector.

The guessing game: higher or lower

Zara thinks of a whole number from 1 to 100, and you guess. After each guess she says "higher", "lower" or "yes". A careless player starts at 1 and climbs, and may need 100 guesses. A careful player always guesses the middle of what is still possible.

Guess 50 first. If she says "lower", every number from 50 to 100 is gone in one answer. About 50 numbers are left, then 25, then 12, 6, 3 and 1. So the careful player never needs more than 7 guesses, because 7 halvings shrink 100 numbers to one.

That is the whole idea of binary search. Compare with the middle of the part still in question, and throw away the half that cannot hold the answer. "Binary" means two: each look splits what is left into two halves. So the number of looks grows with how many times you can halve n, not with n itself.

Sorted is the price you pay

The game works only because the numbers 1 to 100 are in order. When Zara says "lower" after 50, you know every number above 50 is wrong too. Amara's list works the same way only because it is printed from the cheapest up. Here is lower_bound's search for the first 300 on her 16 prices, look by look.

Look 1 found 350 in the middle. On a sorted list, everything to its right is 350 or more, so the first 300 cannot be there. On an unsorted list, a 300 could hide anywhere, and crossing out a half would throw it away. So sorting is the price you pay, once, for searches that take a handful of looks instead of a long walk.

Watch the library halve Amara's list

The C++ library does this search for you. Below are its two most useful searches on Amara's list, step by step. Each step shows the part still in question as [lo, hi): index lo is in, index hi is not. Each compared element is the middle one, at lo + (hi - lo) / 2. Every probe is the one GCC 12's library, libstdc++, really made, printed from a run on Compiler Explorer.

lower_bound wants the first price that is not less than 300. When the middle price is below 300, the answer must be to its right. When it is not below, the answer is that index or to its left. After four looks, nothing is left in question, and the bound sits at index 5.

upper_bound wants the first price that is greater than 300. It makes the same first two looks, then keeps going right past the 300s, and lands at index 8. So on the same list, the two searches stop at the two ends of the 300s: index 5 before them, index 8 after them.

The syntax you need on day one

#include <algorithm>

binary_search(v.begin(), v.end(), x)   true if x is there, false if not
lower_bound(v.begin(), v.end(), x)     the first position whose element is not less than x
upper_bound(v.begin(), v.end(), x)     the first position whose element is greater than x
equal_range(v.begin(), v.end(), x)     both positions at once, as a pair
it - v.begin()                         a position turned into an index
it == v.end()                          the position past the last element: nothing there

So one search answers "is it there?", and the other three answer "where?".

binary_search says yes or no, and nothing else

binary_search answers one question: is an element equal to x anywhere in the range? It prints as 1 for true and 0 for false.

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> price{120, 150, 150, 200, 240, 300, 300, 300,
                      350, 420, 450, 480, 520, 600, 640, 700};
    cout << "a book at 300? " << binary_search(price.begin(), price.end(), 300) << '\n';
    cout << "a book at 310? " << binary_search(price.begin(), price.end(), 310) << '\n';
    return 0;
}

a book at 300? 1
a book at 310? 0

There is a book at 300, and none at 310. But the answer stops there. It does not say where the 300 is, or how many there are, or where 310 would go. Beginners reach for binary_search to find a position, and it has none to give. So use it for a plain yes or no, and ask lower_bound for a place.

lower_bound and upper_bound: two fences around the 300s

Picture a fence you can stand between two neighbouring prices. lower_bound puts it just before the first element that is not less than x. upper_bound puts it just after the last element that is not greater than x. Between the two fences sit exactly the copies of x.

Here are the two fences as a program. Each position is turned into an index by subtracting price.begin(), and the program reads the price just after each fence.

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> price{120, 150, 150, 200, 240, 300, 300, 300,
                      350, 420, 450, 480, 520, 600, 640, 700};
    auto first = lower_bound(price.begin(), price.end(), 300);
    auto after = upper_bound(price.begin(), price.end(), 300);
    cout << "lower_bound(300): index " << first - price.begin() << ", price " << *first << '\n';
    cout << "upper_bound(300): index " << after - price.begin() << ", price " << *after << '\n';
    cout << "copies of 300: " << after - first << '\n';
    return 0;
}

lower_bound(300): index 5, price 300
upper_bound(300): index 8, price 350
copies of 300: 3

lower_bound stopped at index 5 and found a 300 there. upper_bound stopped at index 8, at the 350, one past the last 300. The distance between them is 3: there are three books at 300 taka. So the count of x is always upper minus lower. It is 0 when x is missing, because then both fences stand in the same gap.

equal_range: both fences in one call

equal_range returns the two fences together as a pair: .first is the lower bound and .second the upper one. Module 1's pair works here unchanged.

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> price{120, 150, 150, 200, 240, 300, 300, 300,
                      350, 420, 450, 480, 520, 600, 640, 700};
    for (int x : {300, 310}) {
        auto range = equal_range(price.begin(), price.end(), x);
        cout << x << " at " << range.first - price.begin() << " to "
             << range.second - price.begin() << ", count "
             << range.second - range.first << '\n';
    }
    return 0;
}

300 at 5 to 8, count 3
310 at 8 to 8, count 0

For 300, the pair spans indexes 5 to 8, three books. For 310, both halves of the pair are index 8: an empty stretch, count 0, in the gap where a 310-taka book would go. So equal_range is lower_bound and upper_bound in one call, and lesson 02 counts its comparisons.

From a position to an index, and the end() check

A position is an iterator, not a number. On a vector, it - v.begin() turns it into an index: how many elements stand before it. When every element is less than x, lower_bound returns v.end(), the place after the last element. There is no element there, so compare with v.end() before you read *it.

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> price{120, 150, 150, 200, 240, 300, 300, 300,
                      350, 420, 450, 480, 520, 600, 640, 700};
    for (int x : {310, 100, 800}) {
        auto it = lower_bound(price.begin(), price.end(), x);
        int index = it - price.begin();
        if (it == price.end()) {
            cout << x << ": nothing costs that much; it goes last, at index " << index << '\n';
        } else {
            cout << x << ": goes at index " << index << ", before the " << *it << "-taka book\n";
        }
    }
    return 0;
}

310: goes at index 8, before the 350-taka book
100: goes at index 0, before the 120-taka book
800: nothing costs that much; it goes last, at index 16

The 310-taka book goes at index 8, between the 300s and the 350. A 100-taka book would go first. Nothing on the list costs 800 or more, so lower_bound returned end(), and index 16 is the list's size. So end() is C++'s "not found" for a position, where other languages often use -1.

What it costs: O(log n)

Each look halves the part in question. So the number of looks is about how many times n can be halved before one place is left. That number is the base-2 logarithm of n, written log n. The cost is O(log n), read "order log n". Reading from the front is O(n): in the worst case, every element once.

The table counts the comparisons GCC 12's lower_bound really made. A counting comparator searched for every x from -1 to 2n, on vectors holding 0, 2, 4 and so on. The counts come from one run on Compiler Explorer, GCC 12.2, g++ -O2 -std=c++17, and the same input always gives the same count.

A million prices need at most 20 comparisons, because 20 twos multiplied together make 1048576. Making the list a thousand times longer added only about 10 comparisons. So binary search turns a long walk into a short climb, as long as the range stays sorted.

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> route{3, 8, 11, 17, 24, 31, 40};   // already sorted
    for (int r : {17, 18, 3, 41}) {
        bool stops = binary_search(route.begin(), route.end(), r);
        cout << "route " << r << ": " << (stops ? "stops here" : "does not stop") << '\n';
    }
    return 0;
}

route 17: stops here
route 18: does not stop
route 3: stops here
route 41: does not stop

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> temp{18, 21, 21, 21, 24, 26, 26, 30};   // a week of readings, sorted
    for (int x : {21, 26, 25}) {
        int lo = lower_bound(temp.begin(), temp.end(), x) - temp.begin();
        int hi = upper_bound(temp.begin(), temp.end(), x) - temp.begin();
        cout << x << ": lower " << lo << ", upper " << hi << ", copies " << hi - lo << '\n';
    }
    return 0;
}

21: lower 1, upper 4, copies 3
26: lower 5, upper 7, copies 2
25: lower 5, upper 5, copies 0

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main() {
    vector<string> words{"anchor", "bridge", "candle", "garden", "island",
                         "lantern", "meadow", "puzzle", "rocket", "violin"};
    for (string w : {"garden", "gardens", "harbor", "zebra"}) {
        if (binary_search(words.begin(), words.end(), w)) {
            cout << w << ": on the list\n";
        } else {
            auto it = lower_bound(words.begin(), words.end(), w);
            cout << w << ": not there; it would go at index " << it - words.begin();
            if (it != words.end()) {
                cout << ", before " << *it;
            }
            cout << '\n';
        }
    }
    return 0;
}

garden: on the list
gardens: not there; it would go at index 4, before island
harbor: not there; it would go at index 4, before island
zebra: not there; it would go at index 10

vector<int> cleaned{204, 211, 207, 202, 215, 209};   // in the order Alice cleaned them
for (int room : {207, 202, 215, 211}) {
    cout << room << ": " << (binary_search(cleaned.begin(), cleaned.end(), room) ? "cleaned" : "not yet") << '\n';
}

vector<int> price{120, 150, 200, 300, 350};
if (lower_bound(price.begin(), price.end(), 310) == -1) {
    cout << "no such book\n";
}

vector<int> price{120, 150, 200, 300, 350};
auto it = lower_bound(price.begin(), price.end(), 800);
cout << "index " << it - price.begin() << '\n';
cout << "price " << *it << '\n';

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> price{120, 150, 200, 300, 350};
    cout << lower_bound(price.begin(), price.end(), 300) - price.begin() << '\n';
    cout << upper_bound(price.begin(), price.end(), 300) - price.begin() << '\n';
    return 0;
}

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n = 0;
    cin >> n;
    vector<int> tags(n);   // the tags in the order the items were found
    for (int i = 0; i < n; i++) {
        cin >> tags[i];
    }
    // Get tags ready for a binary search, once.

    int q = 0;
    cin >> q;
    for (int i = 0; i < q; i++) {
        int ticket = 0;
        cin >> ticket;
        // Print yes if an item with this tag is at the desk, no if not.
    }
    return 0;
}

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> leaves(n);   // departure times in minutes after midnight, sorted
    for (int i = 0; i < n; i++) {
        cin >> leaves[i];
    }
    int q;
    cin >> q;
    for (int i = 0; i < q; i++) {
        int t;
        cin >> t;
        // Print how many minutes Alice waits for the next bus. If no bus
        // leaves at t or later today, she waits for the first bus tomorrow.
    }
    return 0;
}

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<long long> amara(n);   // Amara's prices, sorted
    for (int i = 0; i < n; i++) {
        cin >> amara[i];
    }
    int m;
    cin >> m;
    vector<long long> bob(m);   // Bob's prices, sorted
    for (int i = 0; i < m; i++) {
        cin >> bob[i];
    }

    // Find the smallest difference between one of Amara's prices and one
    // of Bob's, and print it.

    return 0;
}

Next, lesson 02 goes through every form of the four calls, one by one, each with its cost and its trap.