Binary Search

Binary search is commonly introduced as a method to search elements in a sorted array. But it’s beneficial as an optimization algorithm too. We can apply this method to specific problems. We’ll only consider functions of a single variable. Binary search works on problems with a constraint with a particular characteristic we’ll know about soon. It also works for special target functions.

Besides those limitations, there are a couple of advantages that make this method very powerful. In the first place, it’s fast. The runtime complexity analysis of the algorithms is beyond our scope, but we’ll briefly refer to it at the end. The second great advantage of binary search is that it even works with unknown functions.

We think those are powers worth having!

Apply binary search

Consider the following optimization problem:

$$\min_x f(x) \\ s.t.: x \in C$$

Let’s focus on the target function $f(x)$. Binary search will only work if $f(x)$ is monotonic.

A function is monotonic when it’s always increasing or always decreasing. It never changes its direction: it always goes up or always down. The following figure shows examples of monotonic and non-monotonic functions.