Binary Search¶

In one sentence

If a yes/no question flips only once as a number grows (yes, yes, …, yes, no, no, …), you can find the flip point by halving the range each time: about \(30\) checks for a range of \(10^9\).

1. What problem does it solve?¶

Example — 1593C · Save More Mice (5-BinarySearch · A, rating 1000)

On a line there is a cat at point \(0\), a hole at point \(n\), and \(k\) mice at points \(x_1, \dots, x_k\) (all between \(0\) and \(n\)). Every second, you move one mouse one step right (a mouse reaching \(n\) is safe), then the cat moves one step right and eats every mouse on its new point. What is the largest number of mice you can save?

Limits: \(t \le 10^4\), \(n \le 10^9\), \(k \le 4\cdot10^5\) (sum over tests).

Input                    Output
3
10 6
8 7 5 4 9 4              3
2 8
1 1 1 1 1 1 1 1          1
12 11
1 2 3 4 5 6 7 8 9 10 11  4

Turn it into a yes/no question. "Can I save \(c\) mice?" If you can save \(c\), you can certainly save \(c - 1\) (just ignore one of them). So the answers look like

\[ \underbrace{\text{yes, yes, …, yes}}_{c = 0, 1, \dots, \text{ans}},\ \underbrace{\text{no, no, …}}_{c > \text{ans}} \]

and we want the last yes.

Checking one \(c\) is easy. Save the \(c\) mice closest to the hole (a farther mouse only needs more moves). Mouse \(i\) needs \(n - x_i\) moves. The cat reaches point \(n\) after \(n\) seconds, and on each of the first \(n - 1\) seconds we make one move before the cat does, so all \(c\) mice are safe exactly when

\[ \sum_{\text{the } c \text{ closest}} (n - x_i) \le n - 1 . \]

2. The math¶

2.1 The invariant¶

Keep a range \([l, r]\) that must contain the answer, and a variable ans holding the best "yes" seen so far. Look at \(mid = \lfloor (l + r)/2 \rfloor\):

check(mid) is yes: the answer is \(mid\) or bigger. Save ans = mid, search \([mid + 1, r]\).
check(mid) is no: the answer is smaller. Search \([l, mid - 1]\).

Each step removes at least half of the range, so after \(s\) steps at most \(N / 2^s\) candidates remain: about \(\log_2 N\) steps in total. When \(l > r\) the loop stops and ans is the last yes.

range size \(N\)	\(4\cdot10^5\)	\(10^9\)	\(10^{18}\)
steps \(\lceil\log_2 N\rceil\)	19	30	60

2.2 Making `check` fast¶

Sort the mice from closest to the hole to farthest and store need[i] \(= n - x\) for the \(i\)-th one. With a prefix sum pre[c] \(= \texttt{need}[1] + \dots + \texttt{need}[c]\), check(c) is just pre[c] <= n - 1, which is \(O(1)\).

2.3 Trace on sample 1¶

\(n = 10\), mice at \(8, 7, 5, 4, 9, 4\). Closest first: \(9, 8, 7, 5, 4, 4\), so need \(= 1, 2, 3, 5, 6, 6\) and pre \(= 1, 3, 6, 11, 17, 23\). We need pre[c] \(\le 9\).

\(l\)	\(r\)	\(mid\)	`pre[mid]`	\(\le 9\)?	action	`ans`
0	6	3	6	yes	\(l = 4\)	3
4	6	5	17	no	\(r = 4\)	3
4	4	4	11	no	\(r = 3\)	3
4	3	—			stop	3

2.4 Two kinds of binary search¶

kind	search space	example
in a sorted array	indices \(0 \dots n-1\)	"how many numbers are smaller than \(x\)?" (5 April)
on the answer	possible answers	"largest \(c\) we can save", "largest \(r\) with sum \(\le k\)"

3. Lesson notes (5, 12 and 15 April)¶

4. Worked solution — Save More Mice¶

"Binary Search Template 1" (largest valid value), with check as a lambda.

#include<bits/stdc++.h>

using namespace std;

using ll = long long;

void solve() {
    ll n;
    int k;
    cin >> n >> k;
    vector<ll> x(k);
    for (int i = 0; i < k; i++) {
        cin >> x[i];
    }

    // closest to the hole first
    sort(x.begin(), x.end(), greater<ll>());
    vector<ll> pre(k + 1, 0);
    for (int i = 1; i <= k; i++) {
        pre[i] = pre[i - 1] + (n - x[i - 1]);
    }

    // can we save the c closest mice?
    auto check = [&](int c) -> bool {
        return pre[c] <= n - 1;
    };

    int lo = 0, hi = k, ans = 0;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        if (check(mid)) {
            ans = mid;
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }

    cout << ans << "\n";
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int T = 1;
    cin >> T;
    for (int i = 0; i < T; i++) {
        solve();
    }
    return 0;
}

5. How to recognise it¶

Ask: "If I knew the answer, could I check it quickly? And if \(c\) works, does \(c - 1\) (or \(c + 1\)) also work?"

phrase in the statement	search for	check
"maximum number / size such that …"	last yes	"is \(c\) achievable?"
"minimum time / cost such that …"	first yes (Template 2)	"is \(T\) enough?"
"for each \(l\), the farthest \(r\) with sum \(\le k\)"	last yes per \(l\)	prefix sum (12 April)

6. Common mistakes¶

The upper bound is too small

Work out the largest possible answer from the limits before choosing r. In Cardboard for Pictures the width can be \(5 \cdot 10^8\).

Moving the wrong way

For "largest yes", yes means go right. For "smallest yes", yes means go left. Trace the loop on a tiny example.

check is not monotone

If yes/no can flip back and forth, binary search silently returns garbage. Convince yourself that "\(c\) works ⇒ \(c - 1\) works".

Printing l or r instead of ans

Our template exists so you never have to reason about where l and r stop. Print ans.

Overflow in check

Sums inside check often need long long, and sometimes an early stop. See Integer Types & Overflow.

7. Practice¶

Problem	Set	Rating	Kind
1593C · Save More Mice	5-BinarySearch · A	1000	last yes (this page)
1883C · Raspberries	5-BinarySearch · B	1000	small cases, careful counting
1850E · Cardboard for Pictures	5-BinarySearch · C	1100	on the answer, stop the sum early
1873C · Target Practice	5-BinarySearch · D	800	warm-up
1907C · Removal of Unattractive Pairs	5-BinarySearch · E	1200	count the most frequent letter
1840D · Wooden Toy Festival	5-BinarySearch · F	1400	smallest waiting time that works
1692E · Binary Deque	5-BinarySearch · G	1200	longest window with sum \(s\)
1538C · Number of Pairs	5-BinarySearch · H	1300	sort, then `lower_bound` / `upper_bound`
1873F · Money Trees	5-BinarySearch · I	1300	prefix sum + binary search
AIO 2019 · Medusa's Snakes	AIO 2019 Q4	—	largest \(x\), greedy check
AIO 2026 · Prime Minister	AIO 2026 Q5	—	largest median

Credits & licenses

§3 joins the binary search notes of 5 April, 12 April (templates 1 and 2, and lambdas) and 15 April (the commented template), unchanged apart from heading levels.
Example, invariant, trace, worked solution, table and mistakes are ours.