*Written by Timon Gehr.*

Contents

The goal of this text is to give an account of binary search that can be applied in more general settings than searching for an element in a sorted array.

Let $f$ be a monotone function mapping the interval $[l_{0}, l_{0}+1,\ldots, r_{0}]$ to $\{0,1\}$. This means that $f$ maps “small” numbers to $0$ and “large” numbers to $1$. The issue is that we don’t know which numbers are still small, and which numbers should already be considered large, but $f$ does. We want to learn all the information that is encoded by $f$.

$\begin{array}{c} x:&l_0&l_0+1&\cdots&l_k-1&{\bf l_k}& {\bf r_k}&r_k+1&\cdots&r_0-1&r_0\\ f(x):&0&0&\cdots&0&{\bf 0}&{\bf 1}&1&\cdots&1&1 \end{array}$The goal of binary search is therefore to determine the cutoff point between small numbers and large numbers without evaluating $f$ too many times.

Binary search finds a sequence of nested intervals $[l_{0},r_{0}]\supset [l_{1},r_{1}]\supset\cdots\supset[l_{k-1},r_{k-1}]\supset[l_k,r_k]$ such that the left borders of the intervals are small, and the right borders are large, and such that $l_k+1=r_k$.

(More explicitly, this means that $l_{0}\le l_{1}\le \cdots l_{k-1}\le l_k<r_k\le r_{k-1}\le \cdots\le r_{1}\le r_{0}$, where for each $i$, either $l_i<l_{i+1}$ or $r_{i+1}<r_i$ and $f(l_{0})=f(l_{1})=\cdots=f(l_{k-1})=f(l_k)=0<1=f(r_k)=f(r_{k-1})=\cdots=f(r_{1})=f(r_{0})$.)

Importantly, note that $l_k$ is the largest number that maps to $0$, while $r_k$ is the smallest number that maps to $1$.

Let $m_i$ be an arbitrary number with $l_i<m_i<r_i$. Note that exactly one of the two intervals $[l_i,m_i]$ and $[m_i,r_i]$ has all the required properties of $[l_{i+1},r_{i+1}]$:

If $f(m_i)=0$, then the left border $m_i$ of the interval $[m_i,r_i]$ maps to $0$, while the right border $r_i$ maps to $1$. If $f(m_i)=1$, then the left border $l_i$ of the interval $[l_i,m_i]$ maps to $0$, while the right border $m_i$ maps to $1$.

Therefore, the following generic strategy will successfully determine $[l_k, r_k]$:

int l = l_0, r = r_0; while (l + 1 != r) { // use some m_i with l_i < m_i < r_i: int m = ...; // TODO: choose m_i if (f(m) == 1) { // f(m) == 1, [l_{i+1}, r_{i+1}] = [l_i, m_i]. r = m; } else { // f(m) == 0, [l_{i+1}, r_{i+1}] = [m_i, r_i]. l = m; } } int l_k = l, r_k = r;

If we want to get a small number of steps $k$ in the worst case, $m_i$ should be guaranteed to cut the size of the interval $[l_i, r_i]$ in half. (It is harder to find the boundary in a longer interval. In the worst case, we will need to search in the longer part. The length of the longer part is minimized if $m_i$ cuts the interval $[l_i, r_i]$ in half.)

There are two choices of $m_i$ that satisfy all the requirements as long as $l_i+1<r_i$:

- $m_i = l_i + \lfloor(r_i - l_i)/2\rfloor$.
- $m_i = l_i + \lceil(r_i - l_i)/2\rceil$.

Picking the first one, we obtain a working binary search algorithm:

int l = l_0, r = r_0; while (l + 1 != r) { // choose m such that l_i < m_i < r_i and // max(r_i - m_i, m_i - l_i) is minimal: int m = l + (r - l) / 2; if (f(m) == 1) { r = m; } else { l = m; } }

Note that binary search never evaluates $f(l_{0})$ and $f(r_{0})$, because their values are already known, by assumption. This can sometimes be convenient, because we can just assume values for $f(l_{0})$ and $f(r_{0})$, but don’t actually need to be able to compute them. (This is used for `lower_bound` below.)

Binary search runs in time $O(\log(r_{0}-l_{0})\cdot T)$, where $T$ is an upper bound on the running time of $f$.

## Examples

**Task**: find the first index into a sorted array $[a_{0},\ldots,a_{n−1}]$ whose value is at least $x$.

**Solution**: use binary search with $[l_{0},r_{0}]=[-1,n]$ and $f(i)=[x\le a_i]$. The result is $r_k$. ($r_k=n$ if no such index exists.)

int lower_bound(vector<int> &a, int x) { int n = (int)a.size(); int l_0 = -1, r_0 = n; // we assume a[-1] = -infinity and a[n] = +infinity int l = l_0, r = r_0; while (l + 1 != r) { int m = l + (r - l) / 2; if (x <= a[m]) { // f(m) = [x <= a_m] r = m; } else { l = m; } } int l_k = l, r_k = r; // we know that a[l_k]<x<=a[r_k]=a[l_k+1]. return r_k; // therefore, r_k is the first index whose value is >=x. }

Note that we have used $a_{-1}=-∞$ and $a_n=∞$ as sentinel values.

`lower_bound` runs in time $O(\log(n))$, because $f$ can be evaluated in constant time $O(1)$.

**Task**: find the last index into a sorted array $[a_{0},\ldots,a_{n-1}]$ whose value is still smaller than $x$.

**Solution**: use binary search with $[l_{0},r_{0}]=[-1,n]$ and $f(i)=[x\le a_i]$. The result is $l_k$. ($l_k=-1$ if no such index exists.)

The code is the same as the one for `lower_bound`, but this time we return `l_k` instead of `r_k`:

int lower_bound_minus_one(vector<int> &a, int x) { int n = (int)a.size(); int l_0 = -1, r_0 = n; int l = l_0, r = r_0; while (l + 1 != r) { int m = l + (r - l) / 2; if (x <= a[m]) { // f(m) = [x <= a_m] r = m; } else { l = m; } } int l_k = l, r_k = r; // we know that a[l_k]<x<=a[r_k]=a[l_k+1]. return l_k; // therefore, l_k is the last index whose value is `<x`. }

**Task**: Given an array of distinct positive integers $[a_{0},\ldots,a_{n-1}]$, find the smallest positive integer not in the array using $O(n\log n)$ time and $O(1)$ auxiliary space.

**Solution**: use binary search with $[l_{0},r_{0}]=[0,n+1]$ and $f(x)=[\lvert\{i\mid a_i\le x\}\rvert<x]$. The result is $r_k$.
We search for the smallest value $x$, such that at least one number between $1$ and $x$ is missing. The function $f$ is monotone. (Why?)

int find_first_missing_positive_number(vector<int> &a) { int n = a.size(); // there are no numbers between 1 and 0: int l_0 = 0; // at least one number between 1 and n+1 must be missing: int r_0 = n+1; int l = l_0, r = r_0; while (l + 1 != r) { int m = l + (r - l) / 2; int num_smaller = 0; for (int y : a) { if (y <= m) { num_smaller += 1; } } // if there are less than m values between 1 and m, // then at least one value must be missing if (num_smaller < m) { r = m; } else { l = m; } } int l_k = l, r_k = r; return r_k; }

Note that there is a faster solution if we are allowed more than constant auxiliary space. Our assumption that there is no number that occurs multiple times is very important, as otherwise the definition of $f$ is incorrect. (Why?)

**Task**: Given a $R\times C$ matrix, find the $H\times W$ contiguous submatrix with the maximal median.
**Solution**: Left as an exercise. (This is IOI 2010 task 3 on day 1.)