2Brute2Best
🔥0

Binary Search Pattern: Algorithmic Intuition, Sub-patterns & C++ Guide

If you can answer "is the answer on the left or the right?" in one check, you can halve the search space every step.

4 sub-patterns · 15 questions

Remember this · Binary Search
Trigger
Sorted data, "minimum X such that…", "maximum X such that…", rotated arrays, answers that are monotonic (if X works, X+1 also works).
Think
Is there a yes/no question whose answers look like NNNNYYYY? Then binary search for the first Y.
Key question
What is my check function, and is it monotonic?
A

What is this pattern?

Binary Search means throwing away half of the remaining options with one check, again and again, until one is left. N options take only about log₂ N checks — a million options need about 20.

It does not really need a sorted array. It needs a yes/no question whose answers, across the search space, look like this:

NO NO NO NO YES YES YES

Once answers are "all NOs, then all YESes", checking the middle tells you which half the first YES is in. That's the whole pattern. A sorted array is just the most common place this shape appears (nums[i] >= target?).

The search space can be:

  • indices of an array (classic, rotated, peak),
  • possible answers (the smallest speed, capacity or day that works),
  • cut positions (where to split two sorted arrays).

Guessing a number between 1 and 100 when the other person says only "higher" or "lower". You'd never guess 1, 2, 3… — you'd guess 50, then 25 or 75, and you'd always win within 7 guesses. Each answer rules out half of what's left.

B

See it move

Find the first index where nums[i] ≥ 23. The shaded part is what's still possible; red cells were ruled out without being looked at.

One check throws away halfnums = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91], target = 23step 1/5
nums
0
1
2
3
4
5
6
7
8
9
2
5
8
12
16
23
38
56
72
91
▲lo
▲hi
≥ 23?
0
1
2
3
4
5
6
7
8
9
NO
NO
NO
NO
NO
YES
YES
YES
YES
YES
State
target
23
lo
0
hi
10 (= n, "none")
Answers look like NO NO … YES YES

Ask "is nums[i] ≥ 23?" for every i and the answers are all NOs, then all YESes. We want the first YES — without asking all 10 questions.

Koko: piles [3, 6, 7, 11], 8 hours. The track is every possible speed; ok? fills in as speeds are checked.

Search the answers, not the inputpiles = [3, 6, 7, 11], h = 8step 1/6
speed k
0
1
2
3
4
5
6
7
8
9
10
1
2
3
4
5
6
7
8
9
10
11
ok?
0
1
2
3
4
5
6
7
8
9
10
Setup
piles
[3, 6, 7, 11]
hours allowed
8
range
1 … 11
Answer is somewhere in 1 … 11

We don't search the piles — we search the speeds. Speed 11 surely works (one hour per pile), and speed 1 is the slowest possible.

C

How do I recognise it?

  • The input is sorted (or sorted then rotated) and you need a value or a position.

  • "Find the first / last position where …", "insert position", "lower bound".

  • "Minimum speed / capacity / days / largest sum such that it's possible" — and checking one guess is easy.

  • The required time is O(log N), or N is huge (10⁹) so you can't even loop over it.

  • You can say "if X works, every bigger X works too" (monotonic).

Looks like Binary Search, but isn't

Find a pair with a target sum in a sorted array
→ Two Pointers

You could binary search each element's partner (O(N log N)), but two pointers does it in O(N) by moving both ends.

Search an unsorted array for a value
→ Linear scan or a hash set

Without a NNNNYYYY shape, checking the middle tells you nothing about which half to keep. Sorting first costs O(N log N) — only worth it for many searches.

Matrix with sorted rows **and** sorted columns (LC 240)
→ Staircase walk from a corner

Rows don't continue each other, so it isn't one sorted list. From the top-right corner each comparison removes a whole row or column: O(m + n).

Minimum cost where checking a guess isn't monotonic
→ DP or greedy

Binary search on the answer only works if "X works ⇒ X + 1 works". If a bigger guess can fail after a smaller one worked, halving throws away real answers.

D

How would I discover it from scratch?

Don't memorise “use binary search”. Ask these questions in order — the pattern falls out.

Check every option one by one: every index for the target, or every speed 1, 2, 3, … until one works. O(N), or O(answer range × cost of a check).

E

Sub-patterns

Same core idea, different rule for “valid”. Learn them in this order.

01

Classic / boundaries

4 questions

A sorted array: find a value, or the first / last position where a condition flips from false to true.

02

Rotated / peak

4 questions

The array isn't fully sorted, but some comparison at mid still tells you which half to keep: one half of a rotated array is always sorted, and a rising slope always leads to a peak.

03

Binary search on the answer

4 questions

You aren't searching the input — you're searching the range of possible answers. Guess one, check it greedily, keep the half that still contains the best answer.

04

2D and partition search

3 questions

Search a sorted matrix as one flat sorted array, or binary search where to cut two sorted arrays so the left parts hold exactly half of everything.

F

Don't mix these up

while (lo <= hi) vs while (lo < hi)

Looking for an exact value that may not exist → <=, and both sides move past mid. Looking for a boundary that always exists → <, with hi = mid so mid stays a candidate.

Binary search on an array vs Binary search on the answer

Is there an array you index into with mid? If mid is a speed, a capacity or a day — something you then test — you're searching the answer range.

Find Minimum in Rotated (LC 153) vs Search in Rotated (LC 33)

153 has no target: compare nums[mid] with nums[hi] to find the drop. 33 has a target: find the sorted half, then ask whether the target falls inside it.

Search a 2D Matrix (LC 74) vs Search a 2D Matrix II (LC 240)

74: each row continues the previous one → one flat sorted array. 240: only rows and columns are sorted → staircase from the top-right corner.

Split Array Largest Sum (LC 410) vs Ship Packages in D Days (LC 1011)

Same problem in different words: packages ↔ numbers, days ↔ parts, capacity ↔ largest part sum. Same range [max, sum], same greedy check, same lo < hi loop.

G

Code templates (C++)

Find a value

Invariant: if the target exists, it's inside [lo, hi]. mid = lo + (hi − lo) / 2 avoids overflow.

exact-template.cpp
// Find target in a sorted array. Returns its index, or -1.
// Invariant: if target exists, it is inside [lo, hi].
int findValue(vector<int>& nums, int target) {
    int lo = 0, hi = (int)nums.size() - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;      // same as (lo + hi) / 2, but can't overflow
        if (nums[mid] == target) return mid;
        if (nums[mid] < target) lo = mid + 1;   // target can only be to the right
        else hi = mid - 1;                      // target can only be to the left
    }
    return -1;
}

First index where a condition becomes true

The workhorse. hi starts at n so "no index works" returns n. Lower bound, upper bound and insert position are all this with a different ok.

boundary-template.cpp
// First index i where ok(i) is true, for answers shaped false...false true...true.
// Returns n if no index works. Example ok: nums[i] >= target (= lower bound / insert position).
int firstTrue(vector<int>& nums, int target) {
    auto ok = [&](int i) { return nums[i] >= target; };
    int lo = 0, hi = (int)nums.size();     // hi = n means "none of them"
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (ok(mid)) hi = mid;             // mid works: the first true is mid or to its left
        else lo = mid + 1;                 // mid fails: the first true is right of mid
    }
    return lo;                             // lo == hi: the boundary
}

Binary search on the answer

Only lo, hi and feasible() change between problems. Make lo the smallest answer that could ever work, hi one that surely works.

answer-template.cpp
// Smallest speed k so that all piles are eaten within h hours (Koko).
// Only the range [lo, hi] and feasible() change between problems.
bool feasible(vector<int>& piles, int h, int k) {
    long long hours = 0;
    for (int p : piles) hours += (p + k - 1) / k;   // ceil(p / k)
    return hours <= h;
}

int smallestWorking(vector<int>& piles, int h) {
    int lo = 1;                                      // smallest answer that could ever work
    int hi = *max_element(piles.begin(), piles.end());  // this one surely works
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (feasible(piles, h, mid)) hi = mid;       // works: maybe something smaller works too
        else lo = mid + 1;                           // fails: everything smaller fails too
    }
    return lo;
}

Rotated sorted array

Compare with nums[hi], not nums[lo], so an array that isn't rotated at all still works.

rotated-template.cpp
// Index of the minimum in a rotated sorted array (distinct values).
int findMinIndex(vector<int>& nums) {
    int lo = 0, hi = (int)nums.size() - 1;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] > nums[hi]) lo = mid + 1;  // the drop is right of mid
        else hi = mid;                           // mid..hi is sorted: the min is mid or left of it
    }
    return lo;
}
Next
Start with Classic / boundaries