Introduction
Binary search is one of those algorithms that's easy to understand the idea of, but often hard to work out the implementation details. For example, should it be $$$\text{lo}=0$$$ or $$$\text{lo}=1$$$? Should I set $$$\text{lo}$$$ to $$$\text{mid}$$$ or $$$\text{mid}+1$$$? Is the answer going to be $$$\text{lo}$$$ or $$$\text{hi}$$$? The questions are endless. Today, I'd like to share with you a perspective I discovered that made it easier for me to implement binary search. It makes the implementation much simpler as you will hardly even have the opportunity to make off-by-one errors. I hope you find it helpful!
Motivating Problem
Suppose you're given an array $$$\text{A}$$$ of $$$0$$$s and $$$1$$$s indexed from $$$1$$$ to $$$n$$$. Additionally, you know:
- $$$A[1] = 0$$$
- $$$A[n] = 1$$$
Your goal is to find consecutive indices $$$\ell$$$ and $$$r$$$ so that:
- $$$1\leq\ell \lt r\leq n$$$
- $$$A[\ell]=0$$$
- $$$A[r]=1$$$
Of course you could loop $$$\ell$$$ from $$$1$$$ to $$$n-1$$$ and compare it with $$$\ell+1$$$, but $$$10^9$$$ operations is quite slow.
Generalizing Using Predicates
I hope you agree that the implementation to the above solution was very clean and essentially wrote itself once you understand the idea. Wouldn't it be nice if every binary search problem could be solved just like this? It turns out that we can do that! The above problem is the quintessential binary search problem. At its very core, binary search is not related to sorted arrays at all.
To generalize this, we have to define a concept called a predicate. A real predicate in math is something abstract, but for us, a predicate is a function from a contiguous sequence of integers $$$\{\ell,\ell+1,\dots,r\}$$$ (where $$$\ell \lt r$$$) to $$$\{0,1\}$$$. Essentially, it allows us to create an array of $0$s and $1$s as in the motivating problem.
Predicate Example
To see an example of how all of this comes together, we'll solve the problem of finding the index of a value in a sorted array; this is the usual problem that motivates binary search. Formally, you're given a sorted integer array $$$A$$$ indexed from $$$1$$$ to $$$n$$$ and an integer $$$v$$$. Your goal is to find the first (i.e. smallest) index of $$$A$$$ where $$$v$$$ occurs.
To set this problem up, we'll define the predicate $$$P$$$ on $$$\{1,2,\dots,n\}$$$ as follows:
