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 $$$0$$$s and $$$1$$$s as in the motivating problem: $$$[ P(\ell),P(\ell+1),\dots,P(r) ]$$$

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 \leq A[i]$$$. To see why this is what we want, notice that finding the first index $$$j$$$ where $$$A[j]=v$$$ is the same as finding consecutive $$$i$$$ and $$$j$$$ such that $$$v \gt A[i]$$$ and $$$v\leq A[j]$$$. This works perfectly fine as long as the first occurrence of $$$v$$$ is not at the beginning of the array, this is because we wanted $$$v \gt A[i]$$$, but $$$j$$$ could be the first index. 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. Generally speaking, we don't have to define our predicate at either endpoint $$$\ell$$$ or $$$r$$$, and we may assume $$$P(\ell)=0$$$ and $$$P(r)=1$$$.

Remark: This problem gives an example of a monotone predicate. This is a predicate where if you increase the input, the output increases (non-strictly) as well. With such a predicate, there can never be multiple consecutive pairs $$$\ell$$$ and $$$r$$$ such that $$$P(\ell)=0$$$ and $$$P(r)=1$$$. Hence, in these cases, our algorithm will always return the only possible answer. The same cannot be said for the next example.

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 instead of 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$$$. After making this reduction, it turns out that the problem is equivalent to having an array $$$A$$$ of odd-length 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;
}

Kattis: Always Know Where Your Towel Is

We can also use the non-monotone predicate idea in this problem. I highly recommend solving (or at least knowing the idea of) CSES: Meet in the Middle first.