Binary Search

Quick Revisit

• USE WHEN: Search space has a monotonic predicate (answer goes from NO to YES) or searching sorted data
• INVARIANT: At every step, the answer lies in [lo, hi]; each comparison halves the interval
• TIME: O(log n) | SPACE: O(1)
• CLASSIC BUG: Off-by-one in loop condition or mid calculation; (lo+hi)/2 overflows—use lo+(hi-lo)/2
• PRACTICE: ../12-practice-ladders/01-ladder-1100-to-1400.md

The single most useful algorithmic technique in competitive programming—halve your search space every step to find answers in $O(\log n)$.

Difficulty: Beginner | Prerequisites: Sorting and Searching | CF Rating Range: 1100–1600 | Contest Frequency: Common (appears in most contests)

---

Contents

• Intuition
• C++ STL Reference
• Implementation (Contest-Ready)
• Operations Reference
• Alternative Implementations
• Problem Patterns & Tricks
• Contest Cheat Sheet
• Common Mistakes & Debugging
• Self-Test
• Practice Problems
• Further Reading
• How to Practice This
• What to Solve Next

---

Intuition

You have a sorted array of 8 integers and a stream of queries asking "is value $x$ in the array?"

  a = [ 2 | 5 | 8 | 11 | 14 | 17 | 21 | 25 ]
        0   1   2    3    4    5    6    7

Query: is 25 in the array?

Your first instinct—scan left to right:

  Compare a[0]= 2 with 25 ... no.    (1 comparison)
  Compare a[1]= 5 with 25 ... no.    (2 comparisons)
  Compare a[2]= 8 with 25 ... no.    (3 comparisons)
  Compare a[3]=11 with 25 ... no.    (4 comparisons)
  Compare a[4]=14 with 25 ... no.    (5 comparisons)
  Compare a[5]=17 with 25 ... no.    (6 comparisons)
  Compare a[6]=21 with 25 ... no.    (7 comparisons)
  Compare a[7]=25 with 25 ... YES!   (8 comparisons)

8 comparisons for one query. Now imagine $q=4$ queries—some hit early, some hit late. Worst case: $8\times 4=32$ comparisons.

Scale this to Codeforces constraints: $n={10}^6$ elements, $q={10}^5$ queries. Linear scan per query gives ${10}^6\times {10}^5={10}^{11}$ comparisons. At roughly ${10}^8$ operations per second, that takes $\sim 1000$ seconds. Time limit is usually 2 seconds.

We scanned past elements we already knew were too small. The array is sorted—we ignored that completely. There has to be a better way.

Comparing the target with the middle element tells you which half to discard—you halve the search space every step, giving $O(\log n)$ instead of $O(n)$.

Analogy: Looking up "search" in a physical dictionary. You don't read page 1, page 2, page 3. You open to roughly the middle—say page 500 of 1000. You see words starting with "M". "Search" comes after "M", so you ignore the first 500 pages entirely. Open to page 750: "R". Still before "S". Open to page 875: "S"! A few more splits and you're there. Each opening eliminates half the remaining pages.

Where the analogy breaks: A real dictionary has alphabetical tabs—you might jump closer to "S" directly. Pure binary search doesn't use that extra structure; it always goes to the exact middle. (Interpolation search exploits the distribution, but its worst case is still $O(n)$, so it's rarely used in contests.)

The deeper insight: binary search isn't about sorted arrays—it's about monotonic predicates. Any time you have a function that goes from "no" to "yes" (or vice versa), binary search finds the boundary in $O(\log N)$. Picture the answer space as a row of switches—all OFF on the left, all ON on the right. You don't know where the boundary is, but every query tells you which side you're on. Binary search finds the exact OFF/ON boundary in $O(\log n)$ queries by always testing the middle of the remaining range.

This is also why binary search is notoriously hard to get right. John Mauchly first described the idea in 1946, but the first bug-free published version didn't appear until 1962. Jon Bentley reported in Programming Pearls (1986) that 90% of professional programmers couldn't write a correct binary search. The overflow bug (lo + hi) / 2 wasn't widely recognized until 2006, when Joshua Bloch found it in the Java standard library. The algorithm is simple to describe and easy to get subtly wrong—which is why knowing your invariant cold matters.

Visual Walkthrough

Same array, same target. This time we use binary search.

  a = [ 2 | 5 | 8 | 11 | 14 | 17 | 21 | 25 ]
        0   1   2    3    4    5    6    7

Target: 25

  Step 1:  lo=0                               hi=7
           [ 2 | 5 | 8 | 11 | 14 | 17 | 21 | 25 ]
             ^              ^                   ^
             lo           mid=3                hi
                            |
                       a[3] = 11
                       11 < 25 ---> discard left half, set lo = 4

  Step 2:                    lo=4              hi=7
           [ .   .   .   . | 14 | 17 | 21 | 25 ]
                              ^         ^      ^
                              lo     mid=5    hi
                                       |
                                  a[5] = 17
                                  17 < 25 ---> discard left half, set lo = 6

  Step 3:                                lo=6  hi=7
           [ .   .   .   .   .    . | 21 | 25 ]
                                      ^     ^
                                      lo   hi
                                   mid=6
                                      |
                                 a[6] = 21
                                 21 < 25 ---> discard left half, set lo = 7

  Step 4:                                      lo=7  hi=7
           [ .   .   .   .   .    .    . | 25 ]
                                           ^
                                        lo=hi=mid=7
                                           |
                                      a[7] = 25
                                      25 == 25 ---> FOUND at index 7!

Operation count:

  Linear scan:   8 comparisons
  Binary search: 4 comparisons
  Speedup:       2x on just 8 elements

The gap explodes as $n$ grows:

  +-------------+------------------+---------------------+
  | n           | Linear scan      | Binary search       |
  +-------------+------------------+---------------------+
  | 8           | 8                | 4                   |
  | 1,000       | 1,000            | 10                  |
  | 1,000,000   | 1,000,000        | 20                  |
  | 10^9        | 10^9             | 30                  |
  +-------------+------------------+---------------------+

With $q={10}^5$ queries on $n={10}^6$: linear gives ${10}^{11}$ ops (TLE). Binary search gives $20\times {10}^5=2\times {10}^6$ ops (instant).

The Predicate Landscape

Binary search works on ANY monotonic predicate, not just sorted arrays. The key insight: your search space is divided into two regions.

Index:     0   1   2   3   4   5   6   7   8   9
Value:     1   3   5   7   9  11  13  15  17  19
P(x)>=10:  F   F   F   F   F   T   T   T   T   T
           |------- FALSE -------|------ TRUE ------|
                                 ^
                           Answer: index 5

The search ONLY needs: the predicate is FALSE on the left, TRUE on the right. Any monotonic predicate works. Binary search finds the boundary.

For "maximize x such that P(x) is true":

P(x)<=15:  T   T   T   T   T   T   T   T   F   F
           |------- TRUE --------|------ FALSE -----|
                                 ^
                           Answer: index 7

The Invariant

+--------------------------------------------------------------+
| INVARIANT: The answer is always in [lo, hi]. Each comparison |
| eliminates at least half the remaining candidates.           |
+--------------------------------------------------------------+

Trace the invariant through the walkthrough above:

• Before Step 1: candidates = indices $\{0,1,2,3,4,5,6,7\}$—all 8.
• After Step 1: we learned $a[3]<25$, and the array is sorted, so indices $0..3$ all hold values $<25$. Candidates = $\{4,5,6,7\}$—4 remain. Half gone.
• After Step 2: $a[5]<25$, so indices $4..5$ are too small. Candidates = $\{6,7\}$—2 remain.
• After Step 3: $a[6]<25$. Candidates = $\{7\}$—1 remains.
• Step 4: one candidate left. Check it. Done.

Why the invariant holds: At each step, $mid$ sits at or near the center of $[lo,hi]$. If $a[mid]<target$, every index in $[lo,mid]$ also has value $<target$ (because the array is sorted), so we safely set $lo=mid+1$. Symmetrically, if $a[mid]>target$, we set $hi=mid-1$. Either way, the answer stays inside the new $[lo,hi]$, and the range shrinks by at least half.

Informal proof—why halving is enough:

Each comparison is a yes/no question—it yields exactly 1 bit of information. To identify one position among $n$ candidates, you need ${\log }_{2}n$ bits. Binary search extracts the maximum possible information per comparison: by asking about the middle element, no matter the answer, at least half the candidates are eliminated.

More precisely:

• Start with $n$ candidates.
• After 1 comparison: at most $\lfloor n/2\rfloor$ candidates remain.
• After 2 comparisons: at most $\lfloor n/4\rfloor$.
• After $k$ comparisons: at most $n/2^k$.
• Set $n/2^k\le 1$, giving $k\ge {\log }_{2}n$.

After $\lceil {\log }_{2}n\rceil$ comparisons, exactly 1 candidate remains. For $n={10}^6$, that is $\lceil {\log }_2({10}^6)\rceil =20$. No comparison-based search can do better in the worst case—this is optimal.

Why does asking about the middle specifically guarantee halving? If you asked about, say, the first quarter, the "left" branch eliminates $1/4$ and the "right" branch eliminates $3/4$. The worst case is the $1/4$ branch—only $25\mathrm{\%}$ eliminated. The middle maximizes the minimum elimination: $\lfloor n/2\rfloor$ elements gone regardless of the answer. This is the information-theoretic optimum for a single yes/no question over a totally ordered set.

Derive It—How You'd Invent Binary Search

Sorted array, unknown target. How would you find it?

Attempt 1: Linear scan—$O(N)$. Check each element left to right.

Key observation: After checking the middle element:

• If middle > target, every element right of middle is also > target (sorted!).
• If middle < target, every element left of middle is also < target.
• Either way, half the remaining elements are gone.

Attempt 2: Check middle, eliminate half—this is binary search.

Why $O(\log N)$? Starting with $N$ elements:

• After 1 step: $N/2$ elements remain
• After 2 steps: $N/4$ elements remain
• After $k$ steps: $N/2^k$ elements remain
• We stop when $N/2^k=1$, so $k={\log }_{2}N$

Complexity proof: Each iteration reduces the search space by at least half. After $k$ iterations, the search space has size at most $N/2^k$. The loop terminates when $hi-lo\le 0$, i.e., the search space is empty. $N/2^k\le 1$ implies $k\ge {\log }_{2}N$. Therefore the number of iterations is exactly $\lceil {\log }_2(N+1)\rceil =O(\log N)$. QED

With the algorithm derived and the complexity proven, the remaining skill is knowing when the algorithm applies.

How to Identify

Binary search on the answer requires a monotonic predicate: a function $\text{check}(x)$ whose truth value flips at most once across the search range.

The test: Can you prove that $\text{check}(x)=\text{true}⟹\text{check}(x+1)=\text{true}$? (Or the reverse: once false, stays false.) If yes, binary search applies.

How to verify monotonicity in practice:

1. Name what the predicate measures. Usually it measures something that only increases (or only decreases) as $x$ grows.
2. Argue the implication. Example: "If we can split the array into $\le k$ segments with max sum $\le x$, then we can certainly do it with max sum $\le x+1$, because every valid split for $x$ is also valid for $x+1$."
3. Check the shape. Across the search range, the predicate output should look like:

  x:        1   2   3   4   5   6   7   8   9  10
  check(x): F   F   F   F   T   T   T   T   T   T
                              ^
                       boundary (answer)

If instead you see F T F T F T, the predicate is not monotonic and binary search gives garbage.

Common monotonic predicates:

Predicate	Why monotonic
"Can we finish in time $\le t$?"	More time only helps. Feasible at $t⟹$ feasible at $t+1$.
"Can we achieve answer $\le x$?"	Relaxing the bound can only help.
"Are there $\ge k$ elements $\le x$?"	Raising $x$ can only include more elements.
"Is $a[i]\ge x$ for sorted $a$?"	Sorted order guarantees the flip happens once.

What the Code Won't Teach You

The real skill is recognizing when binary search applies. The template is straightforward—anyone can code it in 2 minutes. What separates solvers from non-solvers is noticing the trigger: "minimize the maximum," "find the first element satisfying property P where P is monotone," or "answer range is huge but each candidate is cheaply checkable." This pattern recognition develops only through hundreds of problems, not from memorizing templates.

  RECOGNITION MAP -- when you see these, think binary search:

  +---------------------------+-------------------------------+
  | Problem phrase            | Binary search form            |
  +---------------------------+-------------------------------+
  | "minimize the maximum"    | BS on answer (first true)     |
  | "maximize the minimum"    | BS on answer (last true)      |
  | "smallest x such that..." | BS on x (first true)          |
  | "sorted + many queries"   | lower_bound / upper_bound     |
  | "huge range, cheap check" | BS on the answer              |
  +---------------------------+-------------------------------+

The fingerprint to burn into memory: "Minimize the maximum" / "Maximize the minimum" paired with a monotonic-checkable answer means binary search on the answer. A useful mnemonic: PIML—Predicate, Invariant, Midpoint (overflow-safe), Loop-termination. Get all four right and the template never bites you.

Parallel binary search is a powerful advanced technique. When you have $q$ queries, each needing its own binary search, and all check functions share expensive computation, you can run all $q$ binary searches simultaneously. The trigger is recognizable: many queries + shared offline computation. Total cost drops from $O(q\cdot n\log V)$ to $O((n+q)\log V)$.

lower_bound and upper_bound are just binary search with a fixed predicate. lower_bound(a, a+n, val) searches for the first position where a[i] >= val. upper_bound searches for the first position where a[i] > val. Understanding this unifies the three forms—array search, value search, and answer search are all the same algorithm with different predicates.

  THE THREE FORMS ARE ONE ALGORITHM:

  Form 1 -- Array search:
    predicate: "is a[mid] >= target?"
    search space: array indices [0, n)

  Form 2 -- lower_bound(val):
    predicate: "is a[mid] >= val?"         (same as Form 1!)
    search space: array indices [0, n)

  Form 3 -- BS on the answer:
    predicate: "is X feasible?"
    search space: answer values [lo, hi]

  All three: find the first index/value where predicate flips to true.

When to Reach for This

Trigger phrases in problem statements:

• "minimize the maximum ..."—binary search on the answer.
• "maximize the minimum ..."—binary search on the answer.
• "find the smallest $x$ such that ..."—binary search on $x$.
• "sorted array" + lookup/count queries—lower_bound / upper_bound.
• Answer range is huge (${10}^9$, ${10}^{18}$) but each candidate is cheaply checkable—binary search on the answer.

Counter-examples (looks like binary search but isn't):

• Non-monotonic predicate: "Find $x$ where $f(x)=0$" and $f$ oscillates (e.g., a polynomial with multiple roots). Binary search only finds a single false-to-true transition. For unimodal functions, ternary search works; for general functions, you need other methods.
• Need all solutions, not just the boundary: "Find every $x$ where check($x$) is true." Binary search finds one boundary. If the true region is contiguous you can find both endpoints with two binary searches. But if true values are scattered, binary search does not help.
• Unsorted data, single query: "Find target in an unsorted array." Sorting costs $O(n\log n)$, which only pays off when you have multiple queries. For one lookup, linear scan with $O(n)$ is optimal.

---

C++ STL Reference

With the concept clear, here are the standard library functions that implement binary search for you. Know when to use the member versions versus the free-standing ones.

Function / Class	Header	What it does	Time Complexity
lower_bound(first, last, val)	<algorithm>	Iterator to first element $\ge$ val in sorted range	$O(\log n)$
upper_bound(first, last, val)	<algorithm>	Iterator to first element $>$ val in sorted range	$O(\log n)$
binary_search(first, last, val)	<algorithm>	Returns true if val exists in sorted range	$O(\log n)$
equal_range(first, last, val)	<algorithm>	Returns {lower_bound, upper_bound} pair	$O(\log n)$
partition_point(first, last, pred)	<algorithm>	Iterator to first element where pred is false (range must be partitioned)	$O(\log n)$
set::lower_bound(val)	<set>	Member version for set/multiset (use this, not std::lower_bound)	$O(\log n)$
midpoint(a, b)	<numeric>	Overflow-safe (a + b) / 2 (C++20)	$O(1)$
ranges::lower_bound(r, val)	<algorithm>	C++20 ranges version	$O(\log n)$

Key detail: std::lower_bound on a set or map is $O(n)$ because those iterators aren't random-access. Always use the member function .lower_bound() for associative containers.

  lower_bound vs upper_bound on a sorted array with duplicates:

  index:    0   1   2   3   4   5
  a =     [ 2 | 4 | 4 | 4 | 7 | 9 ]

  lower_bound(a, 4):  first element >= 4
            ^
            index 1

  upper_bound(a, 4):  first element > 4
                        ^
                        index 4

  Count of 4s = upper_bound - lower_bound = 4 - 1 = 3

  lower_bound(a, 5):  first element >= 5
                        ^
                        index 4   (points to 7, same as upper_bound(4))

  lower_bound(a, 10): first element >= 10
                              ^
                              index 6   (past-the-end = not found)

---

Implementation (Contest-Ready)

Version 1: Array Binary Search—Minimal Template

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

int main() {
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for (auto& x : a) cin >> x;
    sort(a.begin(), a.end());

    while (q--) {
        int x;
        cin >> x;
        // Find first position >= x
        auto it = lower_bound(a.begin(), a.end(), x);
        if (it != a.end() && *it == x)
            cout << "YES " << (it - a.begin()) << "\n";
        else
            cout << "NO\n";
    }
}

Version 2: Binary Search on the Answer—Minimal Template

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

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto& x : a) cin >> x;

    // Example: minimize the maximum value in some partition.
    // check(mid) returns true if we can achieve answer <= mid.
    auto check = [&](long long mid) -> bool {
        // Problem-specific greedy/DP check goes here.
        // Return true if 'mid' is a feasible answer.
        return true; // placeholder
    };

    long long lo = 0, hi = 1e18;  // adjust bounds per problem
    while (lo < hi) {
        // Invariant: answer is in [lo, hi]
        long long mid = lo + (hi - lo) / 2;
        if (check(mid))
            hi = mid;       // mid works, try smaller
        else
            lo = mid + 1;   // mid fails, need bigger
    }
    // Post-condition: lo == hi == the minimum feasible answer
    cout << lo << "\n";
}

Version 2b: Binary Search on the Answer—Explained

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

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto& x : a) cin >> x;

    // The predicate: "can we achieve an answer <= mid?"
    // Must be monotonic: if check(mid) == true, then check(mid+1) == true.
    // We want the SMALLEST mid where check(mid) is true.
    auto check = [&](long long mid) -> bool {
        // --- Replace with problem-specific logic ---
        // Typically a greedy scan: iterate through the array and verify
        // that the constraint holds when the answer is 'mid'.
        return true;
    };

    // lo = smallest possible answer (often 0 or min element)
    // hi = largest possible answer (often 1e18 or max element * n)
    // Invariant: answer is in [lo, hi].
    long long lo = 0, hi = 1e18;

    while (lo < hi) {
        // Invariant: answer is in [lo, hi], all values < lo are infeasible, all values > hi are suboptimal
        // Overflow-safe midpoint. Equivalent to (lo + hi) / 2.
        long long mid = lo + (hi - lo) / 2;

        if (check(mid))
            hi = mid;       // mid is feasible -> answer <= mid
        else
            lo = mid + 1;   // mid is not feasible -> answer > mid
    }
    // lo == hi == the minimum feasible answer
    cout << lo << "\n";
}

Version 3: Binary Search on Real Numbers

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

int main() {
    // Example: find the smallest x in [0, 1e9] such that f(x) >= target.
    auto check = [&](double mid) -> bool {
        return true; // placeholder
    };

    double lo = 0, hi = 1e9;
    // 100 iterations gives ~2^{-100} relative precision -- more than enough.
    for (int iter = 0; iter < 100; iter++) {
        // Invariant: answer is in [lo, hi], interval halves each iteration
        double mid = (lo + hi) / 2;
        if (check(mid))
            hi = mid;
        else
            lo = mid;
    }
    // Post-condition: lo ~= hi ~= the answer (within ~10^-30 precision)
    cout << fixed << setprecision(9) << lo << "\n";
}

Two Templates, Two Conventions

Template A: while (lo < hi)—loop exits when lo == hi, answer is lo.

• Use when searching for the first position satisfying a condition.
• mid = lo + (hi - lo) / 2 -> avoids right-bias.
• Shrink: hi = mid or lo = mid + 1.

// Template A -- find first true
while (lo < hi) {
    // Invariant: answer is in [lo, hi]
    long long mid = lo + (hi - lo) / 2;
    if (check(mid)) hi = mid;
    else            lo = mid + 1;
}
// Post-condition: lo == hi == first index where check is true
// answer: lo

Template B: while (lo <= hi)—loop exits when lo > hi, answer depends on which you track.

• Use when searching for an exact value or the last position.
• mid = lo + (hi - lo) / 2.
• Shrink: hi = mid - 1 or lo = mid + 1.

// Template B -- find exact or last valid
int ans = -1;
while (lo <= hi) {
    // Invariant: answer is in [lo, hi], best valid seen so far is in ans
    long long mid = lo + (hi - lo) / 2;
    if (check(mid)) { ans = mid; lo = mid + 1; }
    else            hi = mid - 1;
}
// Post-condition: ans = last value where check was true (or -1 if none)
// answer: ans

The critical difference: Template A always converges because hi = mid (not mid - 1) prevents skipping. Template B requires careful tracking of the "last valid" answer in a separate variable. When in doubt, prefer Template A—it has fewer moving parts.

The 4 Boundary Variants—Side by Side

Given sorted array a[] and target value x:

+---------------------------+-------------------+------------------+
| What you want             | STL function      | Manual template  |
+---------------------------+-------------------+------------------+
| First element >= x        | lower_bound       | lo=0, hi=n       |
| First element > x         | upper_bound       | lo=0, hi=n       |
| Last element <= x         | upper_bound - 1   | lo=-1, hi=n-1    |
| Last element < x          | lower_bound - 1   | lo=-1, hi=n-1    |
+---------------------------+-------------------+------------------+

Visual for array [1, 3, 5, 5, 7, 9] with x=5:

Index:       0  1  2  3  4  5
Value:       1  3  5  5  7  9
                  ^     ^
lower_bound ------+     |       index 2 (first >= 5)
upper_bound ------------+       index 4 (first > 5)
last <= 5 = upper_bound - 1 =  index 3
last < 5 = lower_bound - 1 =   index 1

Working code for each variant:

// First >= x (lower_bound)
int lo = 0, hi = n;
while (lo < hi) {
    // Invariant: answer is in [lo, hi], all indices < lo have a[i] < x
    int mid = lo + (hi - lo) / 2;
    if (a[mid] >= x) hi = mid;
    else lo = mid + 1;
}
// Post-condition: lo = first index where a[lo] >= x (or n if not found)

// First > x (upper_bound)
int lo = 0, hi = n;
while (lo < hi) {
    // Invariant: answer is in [lo, hi], all indices < lo have a[i] <= x
    int mid = lo + (hi - lo) / 2;
    if (a[mid] > x) hi = mid;
    else lo = mid + 1;
}
// Post-condition: lo = first index where a[lo] > x (or n if not found)

// Last <= x (upper_bound - 1)
int lo = -1, hi = n - 1;
while (lo < hi) {
    // Invariant: answer is in [lo, hi], all indices > hi have a[i] > x
    int mid = lo + (hi - lo + 1) / 2;  // round up to avoid infinite loop
    if (a[mid] <= x) lo = mid;
    else hi = mid - 1;
}
// Post-condition: lo = last index where a[lo] <= x (or -1 if not found)

// Last < x (lower_bound - 1)
int lo = -1, hi = n - 1;
while (lo < hi) {
    // Invariant: answer is in [lo, hi], all indices > hi have a[i] >= x
    int mid = lo + (hi - lo + 1) / 2;  // round up to avoid infinite loop
    if (a[mid] < x) lo = mid;
    else hi = mid - 1;
}
// Post-condition: lo = last index where a[lo] < x (or -1 if not found)

---

Operations Reference

All binary search variants run in logarithmic time; the dominant cost is usually the check function you supply.

Operation	Time	Space
Binary search on sorted array of $n$ elements	$O(\log n)$	$O(1)$
lower_bound / upper_bound on sorted array	$O(\log n)$	$O(1)$
Binary search on the answer (range $[lo,hi]$)	$O(\log (hi-lo)\cdot C)$	$O(1)$ + check
Binary search on real numbers (fixed iterations)	$O(K\cdot C)$ where $K\approx 100$	$O(1)$ + check
Sorting (prerequisite)	$O(n\log n)$	$O(n)$
partition_point on range	$O(\log n)$	$O(1)$

$C$ = cost of the check() function per call. Typically $O(n)$ or $O(n\log n)$.

---

Alternative Implementations—lo < hi vs lo <= hi

Template 1: while (lo < hi)—find the first position satisfying a predicate:

// Returns the smallest i in [lo, hi) where pred(i) is true
int lo = 0, hi = n;
while (lo < hi) {
    int mid = lo + (hi - lo) / 2;
    if (pred(mid)) hi = mid;
    else lo = mid + 1;
}
return lo; // first true position

Template 2: while (lo <= hi)—classic "find exact value":

int lo = 0, hi = n - 1;
while (lo <= hi) {
    int mid = lo + (hi - lo) / 2;
    if (a[mid] == target) return mid;
    if (a[mid] < target) lo = mid + 1;
    else hi = mid - 1;
}
return -1; // not found

When to use which: Template 1 is safer and more general—it works for any monotonic predicate and always terminates. Template 2 is for exact-match search. Most contest problems use Template 1 (find boundary). Key: in Template 1, lo == hi at termination; in Template 2, lo > hi at termination.

---

Problem Patterns & Tricks

These are the seven recurring shapes binary search takes in contest problems. Each one is worth recognizing on sight.

Pattern 1: Binary Search on the Answer (Minimize Maximum / Maximize Minimum)

The classic. Problem asks "minimize the maximum X" or "maximize the minimum X." Binary search on the answer $X$, and write a greedy check(X) function.

Template: "Can we split array into $\le k$ segments where each segment sum $\le X$?" Greedy left-to-right scan, $O(n)$.

Examples: CF 460C -- Present, CF 1623C -- Balanced Stone Heaps

Worked example—minimize the maximum segment sum:

  PROBLEM: Split a = [7, 2, 5, 10, 8] into k=2 contiguous groups
           to MINIMIZE the MAXIMUM group sum.

  Answer range: lo = 10 (max element), hi = 32 (total sum)

  check(X) = "can we split into <= 2 groups, each sum <= X?"
  Greedy: scan left-to-right, accumulate; start new group when sum > X.

  +------+-------+------------------------------------------+--------+
  | Step | mid   | Greedy trace                             | Result |
  +------+-------+------------------------------------------+--------+
  |  1   | 21    | grp1: 7+2+5=14, +10=24>21 CUT           | TRUE   |
  |      |       | grp2: 10+8=18 <= 21                      |        |
  |      |       | 2 groups <= k=2                    hi=21 |        |
  +------+-------+------------------------------------------+--------+
  |  2   | 15    | grp1: 7+2+5=14, +10=24>15 CUT           | FALSE  |
  |      |       | grp2: 10, +8=18>15 CUT                   |        |
  |      |       | grp3: 8    --> 3 groups > k=2     lo=16  |        |
  +------+-------+------------------------------------------+--------+
  |  3   | 18    | grp1: 7+2+5=14, +10=24>18 CUT           | TRUE   |
  |      |       | grp2: 10+8=18 <= 18                      |        |
  |      |       | 2 groups <= k=2                    hi=18 |        |
  +------+-------+------------------------------------------+--------+
  |  4   | 17    | grp1: 7+2+5=14, +10=24>17 CUT           | FALSE  |
  |      |       | grp2: 10, +8=18>17 CUT                   |        |
  |      |       | 3 groups > k=2                    lo=18  |        |
  +------+-------+------------------------------------------+--------+

  lo == hi == 18.  Answer: 18.
  Split: [7, 2, 5] (sum=14) | [10, 8] (sum=18).  Max = 18.

  Predicate shape:
  X:      10  11  12  13  14  15  16  17  18  19 ... 32
  check:   F   F   F   F   F   F   F   F   T   T ...  T
                                             ^
                                        first true = answer

---

Pattern 2: Binary Search on Real Numbers

Same idea, but the answer is a real number (e.g., minimum time, maximum distance). Use a fixed number of iterations (60–100) instead of lo < hi.

Key trick: Never use while (hi - lo > eps)—it breaks for large values. Fixed iteration count is simpler and more robust.

  WHY eps-BASED TERMINATION FAILS FOR LARGE VALUES:

  lo = 1e15,  hi = 1e15 + 1
  double has ~15 decimal digits of precision.
  At magnitude 1e15, smallest representable gap ~ 0.125.

  while (hi - lo > 1e-9):        <-- NEVER terminates!
    hi - lo = 1.0       -->  continue
    hi - lo = 0.5       -->  continue
    hi - lo = 0.25      -->  continue
    hi - lo = 0.125     -->  continue
    mid rounds to lo    -->  hi - lo STUCK at 0.125 FOREVER

  FIX:  for (int iter = 0; iter < 100; iter++)
    After 100 halving steps, precision ~ 1/(2^100) ~ 1e-30.
    Always terminates.  Always precise enough.

Examples: CF 1118D2 -- Coffee and Coursework (Hard), CF 689C -- Mike and Chocolate Thieves

---

Pattern 3: Binary Search + Greedy Check

The check(mid) function uses a greedy strategy. This is the most common pattern at 1200–1600.

Typical flow:

auto check = [&](long long mid) -> bool {
    int cnt = 0; // greedy counter
    for (int i = 0; i < n; i++) {
        // greedily decide if element i fits within constraint 'mid'
    }
    return cnt <= k;
};

Examples: CF 1283E -- New Year Parties, CF 1132D -- Stressful Training

---

Pattern 4: Binary Search + Prefix Sums

Need to find a subarray or position? Combine binary search with prefix sums. Common for "find the minimum length subarray with sum $\ge S$" type problems.

// Prefix sums are sorted (when all a[i] >= 0), so lower_bound works.
auto it = lower_bound(pre.begin(), pre.end(), pre[i] - target);

Examples: CF 1352D -- Alice, Bob and Candies, CF 1537C -- Challenging Cliffs

---

Pattern 5: Binary Search + Sorting for Pair/Match Problems

Sort the array, then for each element, binary search for its best match.

sort(a.begin(), a.end());
for (int i = 0; i < n; i++) {
    auto it = lower_bound(a.begin() + i + 1, a.end(), target - a[i]);
    // process match
}

Examples: CF 1199C -- MP3, CF 1462D -- Add to Neighbour and Remove

---

Pattern 6: Parallel Binary Search (Advanced)

Multiple queries, each needing its own binary search, but the check function shares expensive computation (e.g., persistent data structures, offline processing).

Instead of running $q$ independent binary searches, process all queries simultaneously: maintain $[l{o}_i,h{i}_i]$ for each query, compute all mids, process events in sorted order, and answer all queries in $O(\log V)$ passes.

Total: $O((n+q)\log V)$ instead of $O(q\cdot n\log V)$.

Examples: CF 739D -- Alyona and a tree

---

Pattern 7: Binary Search on Sorted Matrix Rows/Columns

A 2D matrix where each row or column is sorted. Binary search within each row, or binary search on a value and count how many elements are $\le$ that value across all rows.

// Count elements <= val in a row-sorted matrix
long long count = 0;
for (int i = 0; i < n; i++)
    count += upper_bound(mat[i].begin(), mat[i].end(), val) - mat[i].begin();

Examples: CF 1300C -- Anu Has a Function

---

Contest Cheat Sheet

+------------------------------------------------------------------+
|                     BINARY SEARCH CHEAT SHEET                    |
+------------------------------------------------------------------+
| WHEN TO USE:                                                     |
|   - "Minimize the maximum" / "Maximize the minimum"             |
|   - Monotonic predicate: f(x) = FFFFTTTT, find first T          |
|   - Sorted array lookups                                        |
|   - Answer range is huge but checkable                          |
+------------------------------------------------------------------+
| TEMPLATES:                                                       |
|                                                                  |
|   // Find first true (minimize answer)                          |
|   long long lo = LO, hi = HI;                                   |
|   while (lo < hi) {                                              |
|       long long mid = lo + (hi - lo) / 2;                       |
|       if (check(mid)) hi = mid; else lo = mid + 1;              |
|   }                                                              |
|   // answer = lo                                                 |
|                                                                  |
|   // Find last true (maximize answer)                           |
|   while (lo < hi) {                                              |
|       long long mid = lo + (hi - lo + 1) / 2;  // round UP     |
|       if (check(mid)) lo = mid; else hi = mid - 1;              |
|   }                                                              |
|   // answer = lo                                                 |
+------------------------------------------------------------------+
| COMPLEXITY: O(log(range) * C) where C = cost of check()         |
|                                                                  |
| ITERATION COUNTS (memorize these):                               |
|   log2(10^6)  ~= 20 iterations                                   |
|   log2(10^9)  ~= 30 iterations                                   |
|   log2(10^18) ~= 60 iterations                                   |
|                                                                  |
| So binary search barely adds cost. With an O(N) check and       |
| N = 10^5, BS on answer does 30 x 10^5 = 3x10^6 ops -- trivial.  |
| Even with N = 10^5 and range 10^18: 60 x 10^5 = 6x10^6 -- fine. |
| Binary search is almost "free" on top of whatever check() costs. |
|                                                                  |
| SPACE:      O(1) + whatever check() needs                       |
+------------------------------------------------------------------+
| STL: lower_bound  upper_bound  partition_point  midpoint         |
+------------------------------------------------------------------+

---

Common Mistakes & Debugging

Off-by-One in lo/hi Updates

The #1 source of bugs. Two safe templates:

• Find minimum (first true): lo < hi, hi = mid, lo = mid + 1. Answer at lo.
• Find maximum (last true): lo < hi, lo = mid, hi = mid - 1, but use mid = lo + (hi - lo + 1) / 2 (round up!) to avoid infinite loop.

If you mix these up, you get an infinite loop when hi - lo == 1.

Concrete example of the infinite-loop trap.lo = 3, hi = 4. "Find maximum" template, but without rounding up:

mid = 3 + (4 - 3) / 2 = 3       // floor division
check(3) is true  =>  lo = mid = 3
// lo and hi unchanged!  lo = 3, hi = 4 forever.

Fix: mid = lo + (hi - lo + 1) / 2 gives mid = 4. Now either lo = 4 (done) or hi = 3 (done).

Template cheat table:

Goal           | Loop      | mid formula           | true branch   | false branch
---------------+-----------+-----------------------+---------------+-------------
First true     | lo < hi   | lo + (hi-lo)/2        | hi = mid      | lo = mid + 1
Last true      | lo < hi   | lo + (hi-lo+1)/2      | lo = mid      | hi = mid - 1

When in doubt, use the "first true" template (simpler) and negate the predicate to convert a "last true" search into "first false" minus one.

Integer Overflow in Midpoint

Midpoint overflow. int mid = (lo + hi) / 2 overflows when lo + hi > INT_MAX. This matters when searching in ranges up to $2\times {10}^9$ or when using long long indices.

// WRONG -- overflows for large lo, hi
int mid = (lo + hi) / 2;

// CORRECT -- always safe
int mid = lo + (hi - lo) / 2;

For C++20, std::midpoint(lo, hi) also works correctly.

Wrong Search Direction

• Minimizing? check(mid) == true means hi = mid (try smaller).
• Maximizing? check(mid) == true means lo = mid (try bigger).

Reversing these finds the wrong boundary—not a compile error, just a wrong answer.

Floating-Point Binary Search Infinite Loop

Never write while (hi - lo > 1e-9) for large values—if lo and hi are around ${10}^{15}$, the difference can never reach ${10}^{-9}$ due to floating-point precision. Always use a fixed iteration count: for (int i = 0; i < 100; i++).

Forgetting the Predicate Must Be Monotonic

Binary search only works when the predicate switches at most once from false to true (or true to false). If the predicate is FTFTFT, binary search gives garbage. Verify monotonicity before coding.

Using std::lower_bound on set/map

std::lower_bound(s.begin(), s.end(), val) compiles but is $O(n)$ on non-random-access iterators. Use s.lower_bound(val) for $O(\log n)$.

Debug Checklist

1. Print lo, hi, mid, and check(mid) each iteration.
2. Test with the smallest possible range (e.g., lo = hi - 1).
3. Test with answer at the boundary (lo or hi of initial range).
4. If stuck in infinite loop, check your rounding: minimize uses mid = lo + (hi-lo)/2, maximize uses mid = lo + (hi-lo+1)/2.

Mental Traps

"Binary search is for sorted arrays."

Binary search works on any monotonic structure, not just sorted arrays. "Binary search on the answer"—the most important pattern at 1200+ rating—has nothing to do with arrays. You search the answer space for the boundary between infeasible and feasible.

  WRONG thinking:
    sorted array?  --yes-->  binary search
                   --no--->  can't use BS

  RIGHT thinking:
    monotonic predicate?  --yes-->  binary search
                          --no--->  can't use BS

  Sorted array:     ONE source of monotonicity
  Answer space:     ANOTHER source (and more common at 1200+)
  Prefix sums:      ANOTHER source
  Sorted matrix:    ANOTHER source

"I know the pattern, I'll just code it."

The two templates (find-first-true vs. find-last-true) differ in one place: the midpoint formula. Coding from "I know binary search" without explicitly choosing the template produces infinite loops. Always decide upfront: am I minimizing or maximizing?

  WRONG:
    "I know binary search" --> code mid = (lo+hi)/2 --> infinite loop

  RIGHT:
    Am I MINIMIZING or MAXIMIZING?
        |                        |
        v                        v
    FIRST TRUE                LAST TRUE
    mid = lo+(hi-lo)/2        mid = lo+(hi-lo+1)/2
    true  -> hi = mid         true  -> lo = mid
    false -> lo = mid+1       false -> hi = mid-1

"The check function is obvious once I see the template."

The template is trivial—anyone memorizes it in 5 minutes. The hard part—the part that requires 90% of your thinking—is designing the check function. For a "minimize the maximum" problem, what does it mean for value X to be feasible?

  EFFORT DISTRIBUTION:

  WRONG assumption:
    template ===###========  (50% effort)
    check    ===###========  (50% effort)

  REALITY:
    template =#                (10% effort -- memorized)
    check    =###############  (90% effort -- problem-specific)
                |
                v
        "Can we do X with limit mid?"
        Design a greedy O(n) verifier.
        THIS is where you solve the problem.

---

When Your Solution Is Wrong

• WA (Wrong Answer):
  • Wrong midpoint rounding: mid = (lo + hi) / 2 vs mid = (lo + hi + 1) / 2—if using lo = mid, you need the ceiling to avoid infinite loops
  • Wrong branch condition (check: does lo always move right and hi always move left?)
  • Off-by-one in the answer: is it lo, lo - 1, or hi?
• TLE (Time Limit Exceeded):
  • Infinite loop: range not shrinking because lo = mid with floor division
  • Predicate function itself is too slow (e.g., $O(n)$ predicate makes total $O(n\log n)$)
• WA on edge cases: Test with $n=1$, all-same array, target smaller/larger than all elements.

---

Self-Test

Before moving to practice problems, verify you can do these without looking at the notes above:

• [ ] Write both binary search templates (find-first-true and find-last-true) from memory, getting the midpoint formula right for each.
• [ ] Explain why while (hi - lo > 1e-9) is dangerous for floating-point binary search and what to use instead.
• [ ] Given a problem: "find the minimum number of machines needed so all jobs finish within time T"—identify this as binary search on the answer, state what the predicate is and why it's monotone.
• [ ] State why std::lower_bound on a std::set is $O(n)$, not $O(\log n)$, and how to fix it.
• [ ] Name two trigger phrases in problem statements that strongly suggest "binary search on the answer."
• [ ] Explain why the midpoint formula (lo + hi) / 2 can overflow and give the safe alternative.
• [ ] Trace binary search on a = [1, 3, 5, 7, 9] looking for the first element $\ge 6$. State lo, hi, mid at each step.

Quick Quiz

Q1: Binary search on answer requires what property of the check function?

Answer

Monotonicity. The check function must be monotone—it transitions from false to true (or true to false) at exactly one threshold. This ensures the binary search converges to the boundary. Without monotonicity, there's no single split point to find.

Q2: Why is mid = (lo + hi) / 2 dangerous in C++, and what's the safe alternative?

Answer

When lo and hi are large integers, their sum can overflow. The safe formula is `mid = lo + (hi - lo) / 2`, which avoids the overflow by computing the offset first.

Q3: You're binary-searching on a floating-point answer. Why is while (hi - lo > 1e-9) risky, and what should you use instead?

Answer

When hi and lo are large (e.g., 10^9), floating-point precision means `hi - lo` can never shrink below ~0.125 due to limited mantissa bits, causing an infinite loop. Use a fixed iteration count instead: `for (int iter = 0; iter < 100; iter++)` guarantees termination with ~10^-30 precision.

Q4: std::lower_bound on a std::set runs in $O(n)$, not $O(\log n)$. Why, and how do you fix it?

Answer

`std::lower_bound` uses iterator advancement, which is $O(1)$ for random-access iterators but $O(n)$ for bidirectional iterators (like `set`'s). Fix: use the member function `s.lower_bound(x)`, which traverses the BST in $O(\log n)$.

Q5: A problem says "find the minimum value of X such that you can complete all tasks within time T." What's the binary search setup—what are lo, hi, and the predicate?

Answer

lo = minimum possible X (e.g., 0 or 1), hi = maximum possible X (upper bound from constraints). Predicate: `canFinish(X, T)` returns true if X resources suffice to finish within time T. This predicate is monotone (more resources -> easier), so binary search finds the smallest X where it's true.

---

Designing Test Cases

Before you submit, run your binary search against these cases—they catch the bugs that sample tests won't.

Minimal cases:

• n = 1: Single-element array. Does your search find it? Does it correctly report "not found"?
• n = 2: The smallest array with an actual midpoint decision. Check both target = a[0] and target = a[1].

Edge cases:

• Target at boundaries: Target equals the first element, the last element, or both (all-same array).
• Target not present: Target smaller than a[0], larger than a[n-1], and between two consecutive elements.
• All identical values: a = [5, 5, 5, 5, 5]. Does lower_bound return the first position and upper_bound the last? Off-by-ones love hiding here.
• Large n with target at extremes: n = 10^6, target at index 0 or index n-1. Catches overflow in (lo + hi) / 2.

Stress test (run locally before submitting):

// Generate random sorted array, pick random target.
// Compare binary search result against linear scan.
mt19937 rng(42);
for (int iter = 0; iter < 100000; iter++) {
    int n = rng() % 20 + 1;
    vector<int> a(n);
    for (int& x : a) x = rng() % 50;
    sort(a.begin(), a.end());
    int target = rng() % 50;
    int bs_ans = my_binary_search(a, target);
    int bf_ans = linear_search(a, target);  // simple loop
    assert(bs_ans == bf_ans);
}

Keep n small (<=20) so the brute force is instant, but run many iterations. If your binary search template is wrong, this will catch it within seconds.

---

Practice Problems

#	Problem	Source	Difficulty	Key Idea
1	Binary Search	CF EDU	1100	Pure binary search warmup drills
2	Hamburgers	CF 371C	1300	BS on answer: minimum money to make $k$ burgers
3	Aggressive Cows (SPOJ)	SPOJ	1400	Classic "maximize minimum distance"
4	Present	CF 460C	1500	BS on answer + greedy simulation
5	Magic Powder 2	CF 670D2	1500	BS on answer with resource allocation check
6	Multiplication Table	CF 448D	1600	BS on answer + counting in virtual matrix
7	Stressful Training	CF 1132D	1800	BS on answer + complex greedy check
8	Alyona and a tree	CF 739D	2100	Parallel binary search / BS on tree
9	Factory Machines	CSES	1400	Clean BS on answer, good for practice
10	K-th Number	CF 76A	2000	BS on answer + sliding window check

---

Level-Up Chain

Work through these four levels in order. Each level adds a new dimension to binary search.

Level	Pattern	Problem / Description	Key Idea
1	Find element in sorted array	Binary Search (CF EDU)	Pure binary search on a sorted sequence—nail the lo/hi/mid invariant.
2	Binary search on answer (minimize max)	Aggressive Cows (SPOJ)	The answer is monotonic: if distance $d$ works, any $d^{\prime }<d$ also works. Binary search on the answer itself.
3	Binary search + greedy check	Stressful Training (CF 1132D, 1800)	BS on the answer, but the feasibility check is a non-trivial greedy simulation.
4	Binary search + flow / matching	Binary search on answer + max-flow feasibility check	BS determines a threshold; the check builds a bipartite graph and runs matching or flow to verify feasibility. Common in scheduling and assignment problems.

---

Where Else This Idea Appears

Binary search on the answer is not limited to arrays—the same "monotonic predicate" idea transfers to many domains:

• Graphs: Binary search on the maximum edge weight allowed, then check connectivity via BFS/DFS (e.g., "minimum bottleneck path"). See Dijkstra.
• Geometry: Binary search on a distance or radius, then check if a circle/square covers all points. Common in facility-location and smallest-enclosing-circle problems.
• Strings: Binary search on the length of the longest common substring, then use hashing or suffix arrays to verify. See rolling hash / suffix array techniques.
• Optimization: Many "minimize the maximum" or "maximize the minimum" problems across all topics reduce to BS on the answer + a domain-specific feasibility check.

---

Further Reading

• cp-algorithms: Binary Search—clean writeup with proofs.
• CF EDU: Binary Search course—structured problem set from trivial to hard.
• Topcoder: Binary Search tutorial—classic reference on BS invariants.
• CF Blog: Binary search on the answer—community patterns and examples.
• Prerequisite: Sorting and Searching
• Related: Two Pointers, Prefix Sums
• Practice: Ladder 1100–1400
• Decision guides: Data Structure Selection, DP vs Greedy

---

How to Practice This

Speed Drill—Binary Search on Sorted Array

Set a timer and implement binary search (find index of target in sorted array, return -1 if absent) from scratch. No references.

Attempt	Target	Notes
1st	< 5 min	Focus on getting the lo/hi/mid invariant and termination correct.
2nd	< 3 min	Eliminate off-by-one hesitation—commit to one convention (lo <= hi or lo < hi).
3rd+	< 2 min	Competition-ready. The loop should flow from muscle memory.

Variation Drills

Once basic BS is automatic, drill these essential variants:

Variation	Key change	Practice problem
lower_bound (first >= target)	Return lo after loop; no early exit	CF EDU Binary Search - Step 1
upper_bound (first > target)	Change <= to < in comparison	CF EDU Binary Search - Step 2
BS on answer (minimize max)	BS on result space + feasibility check	Aggressive Cows (SPOJ)

For each: implement, verify on the linked problem, then time yourself.

Practice Strategy

1. Week 1: Drill basic BS + lower_bound daily until you never get off-by-one errors.
2. Week 2: Practice BS on answer—pick one problem per day from the CF EDU course.
3. Week 3: Combine with other techniques (BS + greedy check, BS + graph check).
4. Ongoing: Whenever a problem has a monotonic predicate, immediately think "binary search on the answer."

---

What to Solve Next

After binary search is automatic, branch out to the techniques it pairs with most often:

• Two Pointers—the other $O(n)$ technique for sorted data; know when each fits
• Prefix Sums—binary search + prefix sums handles "find the subarray with sum closest to X"
• Sliding Window—when the predicate isn't globally monotonic but is window-monotonic
• Sorting and Searching—binary search assumes sorted input; revisit custom comparators
• Practice Ladder 1100–1400—graded problems mixing binary search with greedy and implementation