Advanced Binary Search

Written by Timon Gehr.

Contents

Examples

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