Binary search

Binary search finds a number in a sorted array, or the place where it would go, by looking at the middle and throwing away the half that can't hold it. The same loop finds the longest length or the shortest time that still passes a yes/no check. To find the highest point of a function that goes up and then down, use ternary search instead.

Explanation

Seven numbers are written in increasing order: 3, 8, 12, 15, 21, 26, 30. Is 21 among them? Look at the middle number, 15. 21 is bigger, and every number left of 15 is even smaller, so 15 and the three numbers before it are out. Three numbers are left: 21, 26 and 30. Their middle is 26, which is bigger than 21, so 26 and 30 are out. One number is left, and it is 21. That took three looks; reading from the left would take five.

Fig. 1. The numbers 3, 8, 12 and 30 are never read.

Every look throws away about half of what is left, and 10^6 numbers can be halved about 20 times before one is left. So 10^6 numbers need about 20 looks, where reading from the left can take 10^6. This is the logarithmic running time from time complexity.

Here are ten numbers in an array, some of them repeated: 2, 4, 4, 7, 7, 7, 7, 9, 11, 13, at indices 0 to 9. Where is the first 7? This is the same as asking how many numbers are smaller than 7, because all of them stand before it.

Fig. 2. Where is the first 7?

7 appears four times, and the question asks for the first copy. A number can also be missing: 6 is not in the array, but "where would 6 go?" still has an answer.

The natural move is to do what worked on seven numbers: look at the middle and stop as soon as you see a 7. Ten numbers have two middles, at indices 4 and 5; take the left one. Index 4 holds 7, so the search stops and answers index 4, but index 3 holds 7 as well. The search says that 4 numbers are smaller than 7, and there are only 3.

Fig. 3. The middle look finds the 7 at index 4 (blue). The first 7 is at index 3 (green).

So seeing a 7 is not the end of the search: it only tells us that the first 7 is at index 4 or somewhere to its left. To find it, ask every look the same yes/no check: is this number at least 7? Along the array the check says no, no, no, and then yes from index 3 to the end. All the "no"s come first, because the array is sorted. The first 7 is exactly the place where "no" turns into "yes", the turning point.

Keep two marks: the last index known to say "no" and the first index known to say "yes". Before any look nothing is known, so the marks stand just outside the array, one before index 0 and one after index 9. Each look goes to the middle between the marks and moves one mark there: a "yes" moves the right mark, and a "no" moves the left mark. When the marks stand side by side, nothing is left between them, and the right mark is the answer.

This works because the left mark always stands on a "no" and the right mark on a "yes", so the turning point stays between them while every look brings them closer.

This loop is binary search: two marks around the part still unknown, and a look in its middle that moves one of them.

Nothing is known yet: l stands just before index 0 and r just after index 9.

The middle between the marks is index 4. It holds 7, which is at least 7: the check says "yes".

A "yes" means r moves to index 4. Indices 4 to 9 say "yes".

The middle between the marks is index 1. It holds 4, which is less than 7: the check says "no".

A "no" means l moves to index 1. Indices 0 to 1 say "no".

The middle between the marks is index 2. It holds 4, which is less than 7: the check says "no".

A "no" means l moves to index 2. Indices 0 to 2 say "no".

The middle between the marks is index 3. It holds 7, which is at least 7: the check says "yes".

A "yes" means r moves to index 3. Indices 3 to 9 say "yes".

The marks stand side by side at indices 2 and 3, so the first 7 is at index 3.

1/10

Fig. 4. Binary search for the first number at least 7. The dark blue cell is the look, grey cells say "no", light blue cells say "yes". The marks l and r stand on the last known "no" and the first known "yes".

The marks end side by side at indices 2 and 3, so the first 7 is at index 3, and 3 numbers are smaller than 7; index 3 holds 7, so 7 is in the array. The check "is it at least 6?" turns at index 3 as well, but index 3 holds 7, not 6, so 6 is not in the array.

Searching over the answers

Three ribbons are 11, 8 and 5 metres long. You need 5 pieces of the same length, a whole number of metres, and leftovers are thrown away. What is the longest piece you can cut? Pieces of 4 metres work: 2 from the first ribbon, 2 from the second and 1 from the third. Pieces of 5 metres give only 2 + 1 + 1 = 4.

You could try 1, 2, 3, … metres until one fails. That is 5 checks here, but with ribbons up to 10^9 metres it can be 10^9 checks, each going over all the ribbons.

There is no array here, but there is a yes/no check: "do pieces of this length give at least 5 pieces?". A shorter piece never gives fewer pieces, so the check says "yes" for every length up to some point and "no" after it, as Fig. 5 shows. The longest piece is the last "yes", and the same two marks find it. This time "yes" comes first, so the marks swap sides: the left mark stays on a "yes", the right mark on a "no", and the answer is the left mark.

Fig. 5. Lengths up to 4 give at least 5 pieces; length 5 and longer don't. Now l stands on the last "yes" and r on the first "no", and the answer is l.

The left mark starts at 0 metres and the right mark at 12, longer than every ribbon. Looks land between the marks, so 0 and 12 are never checked and don't have to be real lengths. The first look is 6 metres: 2 pieces, "no", so the right mark moves to 6. The next look is 3 metres: 6 pieces, "yes", so the left mark moves to 3.

If even 1 metre gives too few pieces, the left mark never moves, and the answer 0 means "impossible".

Implementation

From here on the left mark is l and the right mark is r. The array a has n numbers in increasing order at indices 0 to n - 1, read into a vector, and x is the number we search for. The check at index m is a[m] >= x. The loop keeps one rule: l is -1 or an index where the check says "no", and r is n or an index where it says "yes".

1. Start: l = -1 and r = n.

2. Look: m = (l + r) / 2. Integer division rounds down, which takes the left of two middles.

3. Check: is a[m] >= x?

4. Move: if yes, set r = m; if no, set l = m.

5. Repeat from step 2 while r - l > 1; the answer is r.

On the main example, l = -1 and r = 10, so the first look is m = (-1 + 10) / 2 = 4, and a[4] = 7, at least 7, moves r to 4. The next look is m = (-1 + 4) / 2 = 1, the look at index 1 from Fig. 4.

The size of the part still unknown is measured by the gap r - l. While the gap is more than 1, m is strictly between l and r, so the program never reads a[-1] or a[n], and no +1 or -1 is needed anywhere.

The program reads n, then n numbers in increasing order, then x. It prints the first index whose number is at least x (n if there is none), and then whether x is in the array. For the main example the input is:

10
2 4 4 7 7 7 7 9 11 13
7

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

int main() {
    // fast input: only needed when there are about 10^6 numbers to read
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    int x;
    cin >> x;

    // start: nothing is known yet
    int l = -1, r = n;
    while (r - l > 1) {
        // look
        int m = (l + r) / 2;
        // check, then move
        if (a[m] >= x) r = m;
        else l = m;
    }
    // answer: the first index where a[r] >= x
    cout << r << '\n';
    if (r < n && a[r] == x) cout << "found\n";
    else cout << "not found\n";
}

A search makes about \log_2 n looks, so it runs in O(\log n) time. With many questions, read each x in a loop and run the search for each one, so q questions cost O(q \log n), after O(n \log n) once if the array has to be sorted first.

The header <algorithm> has this search built in. a.begin() and a.end() mark the start of the vector and the place just after its end. lower_bound(a.begin(), a.end(), x) does what the loop above does: it points at the first number that is at least x, and subtracting a.begin() turns that into an index, so for 7 it gives 3. When no number is at least x, it returns a.end(), index n.

upper_bound(a.begin(), a.end(), x) points at the first number greater than x. For x = 7 that is the turning point of the check "is it at least 8?": index 7. So the 7s fill indices 3 to 6, and there are 7 − 3 = 4 of them.

int first = lower_bound(a.begin(), a.end(), x) - a.begin();
int after = upper_bound(a.begin(), a.end(), x) - a.begin();
int copies = after - first;

binary_search(a.begin(), a.end(), x) only says true or false.

Code for the search over answers

The check is a function ok(m) that returns true if pieces of length x give at least k pieces. The program reads n and k, then the n ribbon lengths, and prints the longest piece length, or 0 if no length works. For the ribbons example the input is:

3 5
11 8 5

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

int n, k;
vector<int> len;

bool ok(int x) {
    long long pieces = 0;
    for (int i = 0; i < n; i++) pieces += len[i] / x;
    return pieces >= k;
}

int main() {
    cin >> n >> k;
    len.resize(n);
    int longest = 0;
    for (int i = 0; i < n; i++) {
        cin >> len[i];
        longest = max(longest, len[i]);
    }

    // start: length 0 and a length longer than every ribbon
    int l = 0, r = longest + 1;
    while (r - l > 1) {
        // look
        int m = (l + r) / 2;
        // check, then move
        if (ok(m)) l = m;
        else r = m;
    }
    // answer: the longest length that still works, 0 if none
    cout << l << '\n';
}

ok is never called with 0, so len[i] / x never divides by zero. For ribbons up to $M$ metres the loop calls ok about \log_2 M times, and each call goes over all n ribbons, so the program runs in O(n \log M).

Answers that are not whole numbers

Suppose you need the number $x$ with x^2 + \sqrt{x} = 18. The check is "is x^2 + \sqrt{x} \ge 18?", and it says "no" below the answer and "yes" from it on. Start with l = 0 and r = 18. Look at 9: 81 + 3 = 84, "yes", so r = 9. Look at 4.5: 20.25 + 2.12 = 22.37, "yes", so r = 4.5. Look at 2.25: 5.06 + 1.5 = 6.56, "no", so l = 2.25.

Here the marks never stand side by side, so the loop makes a fixed number of looks instead. Each look halves the gap, so 100 looks, at the cost of 100 runs of the check, shrink it 2^{100} \approx 10^{30} times: the gap of 18 ends below 10^{-28}. The program reads the right-hand side c, here 18, and r prints as 4.000000 (16 + 2 = 18).

#include <cmath>
#include <cstdio>
using namespace std;

int main() {
    double c;
    scanf("%lf", &c);
    // start: l = 0 says "no", r = c says "yes"
    double l = 0, r = c;
    for (int it = 0; it < 100; it++) {
        // look
        double m = (l + r) / 2;
        // check, then move
        if (m * m + sqrt(m) >= c) r = m;
        else l = m;
    }
    // answer: r
    printf("%.6f\n", r);
}

Correctness proof

The loop keeps the rule from Implementation, its invariant: before every look, l = -1 or a_l < x, and r = n or a_r \ge x.

At the start, both marks are outside the array, so the rule holds. At a look, r - l \ge 2, so l < m < r and $m$ is a real index. If a_m \ge x, then r = m stands on a "yes"; otherwise l = m stands on a "no". Either way the rule still holds, and the gap gets smaller by at least 1, so the loop ends, with r = l + 1.

At that moment a_r \ge x (or r = n). Every index up to $l$ says "no": a_l < x, and the array is sorted, so every number before a_l is at most a_l. So $r$ is the first index with a_r \ge x, the turning point.

Fig. 6. The turning point from "no" to "yes" is always inside the part still unknown (the bracket), between l and r.

When the array is not sorted

The proof used the sorted order in one step: a "no" at $l$ means every index before $l$ says "no" too. Without that, the check can say yes, no, yes, and the index where the search stops says nothing about where $x$ is. Take 6, 1, 8, 3, 9 and x = 3: the check "is it at least 3?" says yes, no, yes, yes, yes. The loop looks at index 2 (8, yes) and index 0 (6, yes), and answers index 0, which holds 6. lower_bound returns index 2, which holds 8, and binary_search says that 3 is not there, though it is at index 3.

Fig. 7. The search looks at the outlined cells and stops at index 0, but 3 is at index 3 (green). The grey "no" at index 1 stands between "yes" cells.

Sort the array first, and if the problem needs the original positions, sort pairs (value, index) instead of the bare numbers.

Common mistakes

• Stopping at the first match (Fig. 3). Search for the turning point instead, with the loop above or lower_bound.

• Mixing loop styles, such as while (lo < hi) with lo = mid, so the loop can look at the same mid forever. Use one style everywhere, while (r - l > 1), and move both marks to m, which is always strictly between them.

• Printing r in a search where "yes" comes first, as on the ribbons, where r ends on a length that fails. The last "yes" is l, so print l.

• Reading past the end when x is larger than every number, so the answer is n (a.end()). Check r < n (or it != a.end()) before reading a[r].

• Counting the pieces in an int: with long ribbons and short pieces the count overflows and the check says "no" by mistake. Count in long long, as the program above does.

Similar algorithms

Two pointers replace many searches when the questions come in increasing order. For example, to count the numbers between a_i and 2a_i for each a_i of a sorted array, you can run one search per element, O(n \log n) in total, or move a single index forward as $i$ grows, $O(n)$.

Ternary search finds the highest or lowest point of a function that goes up and then down. There is no yes/no check that turns once, so binary search does not apply directly.

Set and map have their own s.lower_bound(x), for when numbers are added or removed between the questions.

Practice