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 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.

int l = 1;
int r = n;

while ((r - l) > 1) {
    int m = midpoint(l, r);
    if(A[m]) r = m;
    else l = m;
}

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 just 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 consisting of

Unable to parse markup [type=CF_MATHJAX]

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 (for simplicity, we assume it exists).

To set this problem up, we'll define the predicate: $$$P(i): v \lt = A[i]$$$. To see why this is what we want, notice that we're interested in the first index $$$j$$$ such that $$$v \lt = A[j]$$$, but this means we want consecutive indices $$$i \lt j$$$ such that $$$v \gt A[i]$$$ and $$$v \lt = A[j]$$$. This perfectly translates to $$$P(i) = 0$$$ and $$$P(j) = 1$$$. However in our binary search, we need predicate to first evaluate to $$$0$$$. To get around this, we'll define our predicate on: $$$\{0,1,\dots,n\}$$$ and specifically set $$$P(0) = 0$$$. The code looks like this:

int search(vi &A, int v, int n){
	auto P = [&](int i) -> int {
		if(i == 0) return 0;
		return v <= A[i];
	}

	int l = 0;
	int r = n;
	while((r - l) > 1){
		int m = midpoint(l, r);
		if(P(m)) r = m;
		else l = m;
	}

	return r;
}

Note: It's actually not necessary to define our predicate at $$$0$$$. This is because midpoint(l, r) will always return an integer that's strictly between $$$\ell$$$ and $$$r$$$ as long as their distance is greater than 1.

CSES: Colored Chairs

We'll apply our binary search technique of non-monotone predicates to this CSES problem. Let's imagine arranging the chairs in a line. First, notice that there will always be two adjacent chairs with the same colour (this has to do with the $$$n$$$ being odd condition). To start, we'll use this property to reduce the problem down to being on an array (not in a circle). Specifically, notice that we may assume chair $$$1$$$ and chair $$$n$$$ have different colours. If they have the same colour, then we may simply return $$$n$$$. Now, it turns out that the problem is equivalent to having an array $$$A$$$ containing integers $$$0$$$ and $$$1$$$ such that $$$A[1]\neq A[n]$$$, and we want to find consecutive indices $$$1\leq i \lt j\leq n$$$ such that $$$A[i] = A[j]$$$. Do you see how similar this is to our original motivating problem? The only difference is that we wanted $$$A[i] \neq A[j]$$$, and we knew $$$A[1] = 0$$$ and $$$A[n] = 1$$$. An easy way to fix the former is to consider parity (even or odd) in our predicate. So, we can try: $$$P(i) : A[i] \bigoplus (i \% 2)$$$ However, we want $$$P(0) = 0$$$ and $$$P(1) = 1$$$. So, to fix that we can instead consider: $$$P(i) : A[i] \bigoplus 1 \bigoplus A[1] \bigoplus (i \% 2)$$$. It's not hard to see that $$$P(0) = 0$$$ and $$$P(1) = 1$$$ because we note that $$$A[1] \neq A[n]$$$ by our earlier observation. Now, the implementation is easy:

#include <bits/stdc++.h>
using namespace std;

int get(int i){
    cout << "? " << i << endl;
    char c;
    cin >> c;
    return c == 'R';
}
 
void answer(int i){
    cout << "! " << i << endl;
}
 
int main(){
    int n;
    cin >> n;
 
    // first, we determine if the first and last chairs are the same colour
    int c1 = get(1);
    int cn = get(n);
    if(c1 == cn){
        answer(n);
        return 0;
    }
    
    // otherwise, we binary search on our predicate
    auto P = [&](int i) -> int {
        return get(i) ^ 1 ^ c1 ^ (i % 2);
    };
 
    // template binary search
    int l = 1;
    int r = n;
 
    while((r - l) > 1){
        int m = midpoint(l, r);
        if(P(m)) r = m;
        else l = m;
    }
 
    // now, P(l) = 0 and P(r) = 1 (and they're one apart)
    // so we can report l
    answer(l);
 
    return 0;
}

Generalized Binary Search