a bit of algorithm: Binary Search Your Way!

I have come across a few interesting usage of binary search. As we all know, binary search is usually implemented to fast searching of a key/value in a sorted data structure. However, as not many of us are not aware of (or maybe not that many, but at least me) that there are many subtle or not so obvious uses of binary search for problem solving! Here I'll go through a few of them.

1. Root Finding
While many more efficient algorithms exist out there to find roots of a function, binary search can be regarded as the easiest to implement. The method itself is called "Bisection", which makes use of the following properties:
1. Intermediate Value Theorem: Given a continuous function \(f(x)\), we say that if there exist \(a,b\) such that \(f(a) \leq 0 \leq f(b)\), then we can find \(x \in [a,b]\) such that \(f(x) = 0\).
2. If \(f(a) * f(b) < 0\), then by part 1, \(x\) must be in between \(a\) and \(b\)

So to find a root, we need to:
1. Find 2 values a and b such that f(a) < 0 and f(b) > 0
2. Let \(c = \frac{a+b}{2}\). We check the following:
    2.1 if f(a) * f(c) < 0, then \(x\) must be in between \(a\) and \(c\). So we set b = c and repeat 1.
    2.2 else if f(a) * f(c) > 0, then x must be in between \(a\) and \(b\) instead. We set a = c and repeat 1.

Notice that the loop can go on forever since the algorithm converges quite slowly towards the exact root \(x\). In practice we repeat the process around N = 40 to 50 times to minimize the error to less than \(\frac{1}{2^{N}}\), small enough for many purposes and applications.

2. Guessing (Efficiently)
Sometimes if we know the search space of a problem beforehand, we can use binary search to "guess" the correct answer. However the problem must have the property such that if we know that our guess is not correct, we can determine quickly which side we should take to continue our search. One such problem can be illustrated in this UVa problem:
UVa 12032 - The Monkey and The Oiled Bamboo

The problem can be summarised to a few sentences: Given an array of values \({a_1,a_2,\ldots,a_N}\), find the smallest value \(K\) such that if we compare \(a_i\) with K sequentially from \(i = 1,2,3,\ldots,N\), \(K\) must always be at least \(a_i\), and if \(a_i\) is equal to \(K\), we decrease \(K\) by one and continue.

It may not be obvious that we can apply binary search to the problem, it sounds a lot like a DP problem to me. However, if we observe closely, we'll see that if \(K\) does not satisfy the requirements, \(K\) must be bigger, and vice versa. Hence we can guess for \(K\) using binary search over the search space of at most around \(10^7\), which can be handled pretty quickly by binary search.


There are many more applications of binary search that can be very interesting and subtle. It's always satisfying to notice such things :)