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 while thinking of ways to teach the students at the UTSC Competitive Coding Club about implementing 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.
