Binary Search
I'd like to say that I didn't write this blog on my own. Topcoder's similar post served as an inspiration and the handbook showed me some really interesting ways to implement binary search. Hopefully this gives you more insight into how to apply binary search to problems as well as how to know if binary search is applicable.
I will assume that you already know how to binary search to find a value in a sorted array. You will notice that the problem statements I give is slightly different than the ones on codeforces. Since the only technique we will be covering is binary search, I have to change some constraints to make the problem fit.
Intuition
We are all familiar with the general problem that binary search is applied to: find a value in a sorted array. This application is so familiar that a lot mistaken binary search for a method to search in a sorted structure.
However, in general, binary search can find the exact value of $Y$ for any function $f(x)$ such that:
$$ f(x) = [x \ge Y] $$However, in general, binary search can find the exact value of $Y$ for any function $f(x)$ such that:
The closed bracket in this case denotes that if the predicate inside is true, the function is 1, and it is 0 otherwise. In the much too familiar array search, the function $f(x) = a[x] \ge v$ where v is your search value.
Generally, binary search look something like this:
int binary_search() {
int lo = 0, hi = n-1;
while (lo <= hi) {
int mid = (lo + hi)/2;
if (f(mid)) hi = mid-1;
else lo = mid+1;
}
return lo;
}double binary_search_real() {
double lo = 0, hi = oo;
for (int i = 0; i < T; i++) {
double mid = (lo + hi)/2;
if (f(mid)) hi = mid;
else lo = mid;
}
return lo;
}Basic Applications
In this section we will go over how to use binary search to solve some codeforces problems. For the most part, we will cover a trick that involves guessing and validating the answer.1. Two cakes
For this problem, we are told that we have $a$ pieces of the first cake and $b$ pieces of the second. There are $n$ plates that we need to fill such that no plate contains pieces from both cakes. We need to be able to compute the maximum X such that we can distribute cake pieces so each plate contains at least X pieces of cakes according to the constraint.
Though the actual bounds for $n, a, b$ are small, we want to consider the case where $ n, a, b \le 10^9$. This tells us one important thing: we need an algorithm that is at the very least $O(\sqrt{n})$. This allows us to rule out some other approaches such as greedy (since we will not be trying to fill the plates), dynamic programming, and others. Do not fret if you do not know those techniques, they each will get a post at least later.
The first realization is that suppose you can make it so that each plate contains at least $X$ pieces of cakes, you can make it so that each plate contains at least $X' < X$ pieces of cakes. With this information, formulate $f(x)$ as follows:
$$ f(x) = notvalid(x) $$
$notvalid(x)$ in this case outputs 1 if you cannot make it so that each plate has at least x pieces of cakes. Notice how $f(x)$ is 0 below some value $Y$ and 1 for any value at or above it. We can use this to find the exact value $Y$ for which $Y$ is invalid. It is not hard to see that since every value less than $Y$ is valid that $Y-1$ is the answer (the maximum valid x).
Now we need a way to find $f(x)$ or in this case, $nonvalid(x)$. We know that since each plate has at least x pieces of cakes that we can make a maximum of $\lfloor \frac{a}{x} \rfloor$ plates with only the first cake and $\lfloor \frac{b}{x} \rfloor$ plates with the second. Since the number of plates is $n$, we have that if x is not valid if:
$$ \bigg\lfloor \frac{a}{x} \bigg\rfloor + \bigg \lfloor \frac{b}{x} \bigg\rfloor < n$$
Therefore, we have that:
$$ f(x) = \bigg[\bigg\lfloor \frac{a}{x} \bigg\rfloor + \bigg \lfloor \frac{b}{x} \bigg\rfloor < n\bigg]$$
In this case, we can binary search for $Y$ using this $f(x)$. Notice how in this problem we are merely guessing the answer and checking if it is right, as opposed to deriving an expression for it. In more complicated problems, this will prove much more powerful than straight math. Since calculating $f(x)$ is $O(1)$, we have that this solution is $O(\log{n})$.
2. Bombing
In this problem, we are commanded to drop a warhead at the location $(x_0, y_0)$ to destroy K of the N buildings in the area. This problem is quite difficult with binary search alone so we will only consider it without K, that is, now we want to destroy all buildings.
We are given the coordinates of all the buildings as well as a tolerable failure rate of $\epsilon$. We want the explosion radius to be large enough so that the probability that we do not destroy all buildings is less than or equal to $\epsilon$. To minimize cost, we want to find the minimum explosion radius needed.
How do we know the probability of one building being destroyed? If the building is within the blast radius of the warhead, it will certainly get destroyed. Suppose we have a warhead with explosion radius $R$ and a building $D > R$ distance away, the probability of that building being destroyed is:
$$ P(D,R) = e^{1-\frac{D^2}{R^2}}$$
Now this formula seems a little complicated. You might wonder what it means, and why the formula is that way. The reality is: we simply don't care. It is just a formula, do not read into it.Back to the problem. We notice a property that allow us to apply binary search to the problem, namely that if a warhead of radius $R$ has failure rate of at most $\epsilon$, then any warhead of radius $R + \Delta$ where $\Delta$ is positive, has a failure rate of at most $\epsilon$. In other words, increasing the radius only make you more successful.
We can then formulate $f(x)$ as follows:
$$ f(R) = [F(R) \le \epsilon] $$
Where $F(R)$ denotes the failure rate. Notice how $f(x)$ is 0 for values less than a number $Y$ and 1 for anything equal to or higher. $Y$, in this case, $Y$ is our answer.
We need to find a formula for $F(R)$. Since directly calculating the failure rate is hard, what we could do is find the success rate and subtract it from 1.
$$ F(R) = 1 - \prod_{(x,y) \in B} {P(\sqrt{(x-x_0)^2 + (y-y_0)^2}, R)}$$
The $\sqrt{(x-x_0)^2 + (y-y_0)^2}$ expression looks intimidating, but it is just the distance formula. Overall, we have an $O(n)$ method for computing F(R) and therefore an $O(N\log{M})$ method to find the answer, where $M$ is our guess to the maximum radius needed. A good upper bound on the radius would be the distance between $(x_0,y_0)$ and the furthest point, since any radius above that have 0 probability of failure.
Caveats
Sometimes, the nature of the problem does not allow for binary search, even if it asks you to find some minimum or maximum value. Let's do an example:
Dima and Trap Graph
In this problem we have a building with some security doors between rooms such that if the door is configured to $(l,r)$ and you have a key $k$ then you can only go through the door (in both directions), if $l \le k \le r$.In the problem we want to find the longest continuous series of numbers $(a,b)$ such that if you have any key in the range from $a$ to $b$, then you can get from room 1 to room N through a series of doors. However, we are interested in the maximum key $k$ such that you can use such key to get from room 1 to room N.
This maximum key $k$ cannot be binary searched. Consider a building with only two rooms and one door connecting the two with configuration $(2, 10)$. The maximum key is 10 but that does not mean that for any key value of less than 10, you can reach room 2 from room 1. Be aware of this pitfall when you are looking at an optimization problem.
Just because you cannot binary search a problem does not mean that it is the end of the world. Do give this problem a try if you find it interesting. The prerequisites are basic graph theory and shortest path.
Harder Problems
These are some harder problems that involves binary search. There will be less detailed explanations on the account that you should be able to deal with the minor details on your own. You might find these difficult to follow if you have not done a lot of competitive programming. In that case, I recommend doing the practice problems listed below and come back to this at a later date.
1. Elongated Matrix
In this problem we can freely order the rows of this matrix. For an integer K, the matrix is K-valid if adjacent elements in its column-order traversal differs by at least K. More formally, if we have a matrix A and its column-order traversal be $a_0, a_1, a_2, ... a_{nm-1}$ then we have that:
$$ \forall_{0 \le i < nm}. |a_i-a_{i+1}| \ge K$$
We want to find the maximum value of K for which we can reorder the rows of the input matrix to make it K-valid. The bounds are such that $ n \le 16, m \le 10^4, 2 \le nm$ and $1 \le a_i \le 10^9$.
The important observation for this problem is that if we can reorder and make A K-valid, we can make it (K-1)-valid. With this, we can use dp to calculate if there is a reordering of rows such that each column is valid and that it starts with row a and end with row b. This can be done in $O(n^2 2^n)$ given that we do some preprocessing to tell if row b can immediately followed row a. Such precomputation is doable in $O(n^2 m)$. After this, we just need to validate if a can be the first column and b can be the last column. A bit more precomputation will suffice.
2. Simple Skewness
In this problem, we are given an array of integers. We are to choose a subset of the elements of the array with the maximum skewness. Skewness of a list is defined as its mean minus its median. The bounds is such that $n \le 2 \cdot 10^5$.
To solve this problem, we need to know how binary search applies to finding the extreme values of a bitonic function. A bitonic function is one that initially increases then decreases, or initially decreases then increases. The $x^2$ function is bitonic, and so is the utility function in economics (if anyone does economics).
We know that a bitonic function $F$'s derivative, $F'$, is monotonic and crosses 0 at the extreme value (max or min) of $F$. If $F$ is discrete, then $F(x)-F(x-1)$ is monotonic. We can use this property to binary search for when the function crosses 0 to figure out the maxima.
Back to the problem. We can prove that there exist an optimal solution such that the number of integers in the subset is odd. We do this by considering an even subset and throwing out one of the middle element to result in at least as good if not better skewness.
Now suppose the array of integers, $a$, is sorted, and you want to fix the median at $a_i$. Say your subset consists of $2k+1$ elements. Clearly, they will be: $a_{i-k}, a_{i-k+1}, ... a_{i-1}, a_{i}, a_{n-k}, a_{n-k+1}, ...a_{n}$, since you want to maximize the mean. Let $f_i(k)$ denote the average of $a_{i-k}, a_{i-k+1}, ... a_{i-1}, a_{i}, a_{n-k}, a_{n-k+1}, ...a_{n}$, we can see that $f_i(k)$ is increasing then decreasing.
This stems from the fact that $a_{i-k}+a_{n-k} \le a_{i-k+1}+a_{n-k+1}$. When you perform a weighted average of $a_{i-k}+a_{n-k}$ and $f_i(k-1) \cdot 2k-1 $, there comes a point where $\frac{a_{i-k}+a_{n-k}}{2} < f_i(k-1)$ so taking the weighted average will result in a number less than $f_i(k-1)$.
This means we can binary search for the maxima in $O(\log{n})$ provided we can find $f_i(k)$ in $O(1)$ time, which can be done with a little precomputation. Trying all median give an $O(n \log{n})$ solution.
Practice Problems:
These are some easy/medium problems involving binary search:
Here are some more challenging problems that involves techniques other than binary search:
Comments
Post a Comment