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
Hint
The check for the limit G: go from the left and add elements to the current part until the sum exceeds G; then start a new part. If at most k parts are needed, G is enough. The lower bound is the largest element, the upper bound is the sum of all of them.
Solution (C++)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n, k;
vector<long long> a;
bool canDo(long long G) { // can it be split into <= k parts with a sum <= G?
int parts = 1;
long long sum = 0;
for (long long x : a) {
if (sum + x > G) { // x does not fit into the current part
parts++;
sum = 0;
}
sum += x;
}
return parts <= k;
}
int main() {
cin >> n >> k;
a.resize(n);
long long lo = 0, hi = 0;
for (auto &x : a) {
cin >> x;
lo = max(lo, x); // every part must hold the largest element
hi += x; // one part with all the elements
}
long long 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;
}
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
Hint
Sort the positions. The check for the distance D: put a router in the first house, and then greedily in every next house that is at least D away from the last router. If at least c routers have been placed, D is achievable. We are looking for the largest achievable D.
Solution (C++)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n, c;
vector<long long> x;
bool canDo(long long D) {
int placed = 1;
long long last = x[0];
for (int i = 1; i < n; i++) {
if (x[i] - last >= D) { // far enough: place a router
placed++;
last = x[i];
}
}
return placed >= c;
}
int main() {
cin >> n >> c;
x.resize(n);
for (auto &v : x) cin >> v;
sort(x.begin(), x.end());
long long lo = 1, hi = x[n - 1] - x[0], answer = 0;
while (lo <= hi) {
long long mid = lo + (hi - lo) / 2;
if (canDo(mid)) { answer = mid; lo = mid + 1; } // a larger one may work too
else hi = mid - 1;
}
cout << answer << endl;
return 0;
}
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?
Podešavanja kolačića
Koristimo kolačiće da bismo vam pružili najbolje moguće iskustvo. Takođe nam omogućavaju da analiziramo ponašanje korisnika kako bismo stalno poboljšavali veb lokaciju za vas.