__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 :)