Binary Search on the Answer

Lesson 3 of 4 · Binary search

Binary search is not only for searching in an array. If it is easy to check whether some number is a good enough answer, but hard to calculate it directly, we look for the answer with binary search over all the possible values. This is one of the most common techniques at district and national competitions.

Before you start: prerequisites – binary search, greedy algorithms.
How to learn: type in and run every example, and solve the tasks at the end on your own first; open the hint and the solution only after that. All programs are in C++.

The idea: a monotonic check

Suppose we have a function canDo(x) that answers yes/no and has the property of monotonicity: if the answer is "yes" for some x, then it is "yes" for every larger x as well. Then the values look like this:

x:         1    2    3    4    5    6    7    8
canDo(x):  no   no   no   no   yes  yes  yes  yes
                               ^ we are looking for the first "yes"

We find the boundary between "no" and "yes" with binary search, with only log₂(range) calls of the function canDo.

// the smallest x from [lo, hi] for which canDo(x) is true (assumption: canDo(hi) is true)
long long lo = 1, hi = 1000000000, answer = hi;
while (lo <= hi) {
    long long mid = lo + (hi - lo) / 2;
    if (canDo(mid)) {
        answer = mid;       // mid is good; try smaller
        hi = mid - 1;
    } else {
        lo = mid + 1;       // mid is not good; we need larger
    }
}

Example 1: machines

The task. A factory has n machines; machine i needs t[i] seconds for one product, and they all work at the same time. What is the shortest time in which they can make P products in total? (n ≤ 2·105, t[i], P ≤ 109)

The check: in a given time T machine i makes T / t[i] products. If the sum is at least P, the time T is enough. The more time there is, the more products there are – the check is monotonic. The upper bound: the fastest machine alone makes P products in min(t) · P seconds.

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

int n;
long long P;
vector<long long> t;

bool canDo(long long T) {              // are at least P products made in T seconds?
    long long total = 0;
    for (int i = 0; i < n; i++) {
        total += T / t[i];
        if (total >= P) return true;   // stop early, also so that the sum does not overflow long long
    }
    return false;
}

int main() {
    cin >> n >> P;
    t.resize(n);
    for (auto &x : t) cin >> x;

    long long lo = 1, hi = *min_element(t.begin(), t.end()) * P, answer = hi;
    while (lo <= hi) {
        long long mid = lo + (hi - lo) / 2;
        if (canDo(mid)) { answer = mid; hi = mid - 1; }
        else lo = mid + 1;
    }
    cout << answer << endl;
    return 0;
}

Example

Input

3 7
3 2 5

Output

8

For this example: in T = 8 the machines make 2 + 4 + 1 = 7 products, and in T = 7 only 2 + 3 + 1 = 6. Complexity: O(n · log(min(t)·P)) ≈ 60 · n operations.

Example 2: a saw (the largest good x)

The task. Trees with heights h[i] are given. A saw is set to the height H and cuts off everything above it: a tree of height h > H gives h − H metres of wood. What is the largest height H with which at least M metres are obtained?

Here the check is monotonic in the other direction: the lower the saw, the more wood there is. That is why we look for the last "yes": when mid is good, we remember it and go right.

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

int main() {
    int n;
    long long M;
    cin >> n >> M;
    vector<long long> h(n);
    for (auto &x : h) cin >> x;

    long long lo = 0, hi = *max_element(h.begin(), h.end()), answer = 0;
    while (lo <= hi) {
        long long H = lo + (hi - lo) / 2;
        long long wood = 0;
        for (long long x : h)
            if (x > H) wood += x - H;
        if (wood >= M) { answer = H; lo = H + 1; }    // enough: try a higher saw
        else hi = H - 1;                               // too little: lower the saw
    }
    cout << answer << endl;
    return 0;
}

Example

Input

4 7
20 15 10 17

Output

15

With H = 15 we get 5 + 2 = 7 metres, and with H = 16 only 4 + 1 = 5.

Binary search over real numbers

When the answer is a real number, instead of lo <= hi we repeat the step a fixed number of times (for example 100). Every step halves the interval, so after 100 steps the error is negligible. Example: the square root of a number without the function sqrt.

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

int main() {
    double x;
    cin >> x;                          // x >= 1
    double lo = 0, hi = x;             // the root is in [0, x]
    for (int k = 0; k < 100; k++) {
        double mid = (lo + hi) / 2;
        if (mid * mid >= x) hi = mid;  // mid is large enough
        else lo = mid;
    }
    cout << fixed << setprecision(6) << hi << endl;
    return 0;
}

For the input 2 the program prints 1.414214. Binary search over real bounds is also used in the task Circular zones.

How to recognise such a task?

  • The smallest or the largest value of something is asked for (time, length, height, capacity).
  • For a given value it is easy to check whether it is "enough" – usually with one pass through the array, often greedily.
  • If a value is enough, every larger (or every smaller) one is enough too.

Common phrasings: "minimise the maximum" (splitting an array into k parts with the smallest largest sum) and "maximise the minimum" (placing cows/routers so that the smallest distance is as large as possible).

Practice tasks

Every task has an example, a hint and a solution. The solutions have been checked on the examples from the text.

TASK 01Difficulty: medium

Splitting an array into k parts

An array of n positive numbers has to be split into at most k consecutive parts so that the largest sum of a part is as small as possible. Print that smallest possible largest sum. (1 ≤ k ≤ n ≤ 105, numbers up to 109)

Example 1

Input

5 3
2 4 7 3 5

Output

8

Example 2

Input

4 1
1 2 3 4

Output

10
TASK 02Difficulty: harder

Placing routers

There are n houses on a street at the positions x[i]. c routers have to be placed in some of the houses so that the smallest distance between two routers is as large as possible. Print that largest possible smallest distance. (2 ≤ c ≤ n ≤ 105, positions up to 109)

Example

Input

5 3
1 2 8 4 9

Output

3
Common mistakes and tips
  • Check the direction of monotonicity: are you looking for the first "yes" (go left when it is good) or the last "yes" (go right)?
  • Choose the bounds so that the answer is surely in [lo, hi].
  • Use long long – products like min(t) · P easily exceed 2·109.
  • In the check, stop adding as soon as the goal is reached, so that the sum does not overflow.

Check your knowledge

Open the quiz

Binary search on the answer

1. What property must the check canDo(x) have?




2. The range of possible answers is from 1 to 10⁹. About how many times is the check called?




3. The largest value for which the answer is "yes" is asked for. When mid is good, what do we do?