Binary Search is NOT About Searching

Every one of us learned binary search the same way. We have a sorted array. Want to find a specific value x in it. We compare x to the middle element, throw away half the array, and repeat. O(log n). Done. The textbook gives you the algorithm, We implement it once or twice, and from that point on we reach for it whenever the words "sorted array" appear.

This is correct, but it is the least interesting thing binary search does.

The deeper truth — the one most courses skip — is that binary search isn't really about searching at all. It is a technique for inverting any monotonic predicate. The sorted-array case happens to be one instance of this, and a rather a boring one. The interesting instances are problems that don't look like search problems at all: how many days to ship?, what eating speed is fast enough?, what is the median of two arrays?, what is √2 to six decimal places? All of these are binary search problems, and none of them have a sorted array in sight.

This article is about getting from the boring case to the interesting ones — and watching the framework do the lifting along the way.

1. The Problem

You have a sorted array of n integers, A. You have a target value x. Return the index i such that A[i] == x, or report that no such index exists.

A small concrete example. Let A = [1, 4, 7, 11, 13, 18, 22, 30] and x = 13. The answer is i = 4.

This is the kind of problem every textbook uses. It is what people mean when they say "binary search." Most programmers can implement it from memory: maintain two pointers lo and hi, look at the middle element, throw away the half that can't contain x, repeat. After at most ⌈log₂(n)⌉ iterations the search space is empty, and we either found x or we didn't.

This version of the problem is so familiar that it's worth pausing to notice something subtle: how little of the problem statement we are actually using. The array is "sorted." That's it. We do not use the array's data type, the gaps between elements, the size of the integers, the fact that they happen to live in a contiguous block of memory. We use one structural fact — sortedness — and discard the rest.

Three iterations to find x = 13 in an 8-element array. The midpoint comparison eliminates half the array each time. Correct, fast, and — as the rest of this article will argue — the least interesting use of the technique.

As we'll see in Section 5, how we will apply binary search, when we don't even use sortedness in the way you'd expect.

2. What We Observe

Before any algorithm, look at the input.

The array is sorted. State this more precisely: it is monotonically non-decreasing. For any two indices i < j, we have A[i] ≤ A[j]. This is a richer statement than "sorted" because it tells us something specific about a predicate defined on the array.

Define the predicate P(i) = (A[i] ≥ x). Because the array is monotonically non-decreasing, this predicate is monotonic on the index i: once it becomes true at some index, it stays true for all larger indices. There is some critical index — call it the boundary — where P transitions from false to true. For our example array and x = 13:

i:     0   1   2   3   4   5   6   7
A[i]:  1   4   7   11  13  18  22  30
P(i):  F   F   F   F   T   T   T   T
                       ↑
                    boundary

If we can find this boundary, we have solved the original problem: index 4 is where P first becomes true, and that index either contains x or proves x is absent.

P(i) = (A[i] ≥ 13) rendered as a strip beneath. The values are just one way to produce the F → T transition; what binary search actually consumes is the transition itself.

Here is the third and important observation, and the one that will eventually break the article open: the only thing about a "sorted array" that binary search actually uses is that some predicate is monotonic over its indices. Not the values. Not the gaps. Not even the array. Just the monotonicity. Everything else is incidental to a problem that happens to be conveniently shaped.

3. How We Decompose

Let's restate binary search as a composition of two parts.

Part one is the predicate: a function that, given a candidate index (or candidate value, in the more general case), tells you whether the boundary lies to its left or its right. In the textbook problem, the predicate is P(i) = (A[i] ≥ x). It is monotonic — that's the structural fact we observed — and it is cheap to evaluate (one comparison, O(1)).

Part two is the halving loop: keep two pointers lo and hi bracketing the boundary, evaluate the predicate at the midpoint, discard the half that can't contain the boundary. This is the part most courses focus on, and it's the part that's the same in every binary search anyone has ever written. There is nothing to think about in the loop.

The thinking is in the predicate.

The article has a thesis-in-miniature that's worth repeating because it will come up several more times before we finish: the predicate is the thinking. The loop is the typing.

What does this decomposition buy us? It lets us notice that the structure of binary search has nothing inherently to do with arrays. We picked an array because it's a convenient shape — indices are integers, midpoints are easy, comparisons are cheap. None of those properties are intrinsic to binary search itself. As we'll see, the same loop works on integer intervals, real intervals, even partition positions in a hypothetical merged array.

The two parts of every binary search. The loop is the same in every implementation that ever shipped. The predicate is where the engineering judgment lives.

4. What the Constraints Tell Us

The textbook problem typically comes with constraints like n ≤ 10⁵ and use O(log n) time, O(1) extra memory. Each of these is doing work.

The size constraint, n ≤ 10⁵, is permissive — it allows anything from O(n) to O(n log n). It does not, by itself, force binary search.

The O(log n) constraint is the one that does. It rules out linear scan. It demands an algorithm that halves the search space at each step. And once we accept that we must halve, we are immediately committed to having a monotonic predicate — without one, we can't tell which half to halve.

A subtler implication of the O(log n) budget: evaluating the predicate must be cheap. The total cost of binary search is O(T_P · log |D|), where T_P is the cost of one predicate evaluation and |D| is the size of the domain. For the textbook problem, T_P = O(1) (a single array lookup and comparison), so the total cost is O(log n). For the binary-search-on-the-answer problems we'll meet in Section 9, the predicate is itself a simulation — and its cost matters. In Capacity to Ship, evaluating the predicate at a candidate capacity costs O(n), making the total cost O(n log W) where W is the answer space's width. Still much better than the brute alternatives.

The constraint we are not given explicitly — but which does all the structural work — is monotonicity. Without it, halving has no meaning. Half of an arbitrary predicate is just half of an arbitrary predicate. Monotonicity is what lets us extract information from a single midpoint evaluation.

The cost model. When the predicate is O(1), binary search is "the log algorithm." When the predicate is a simulation, the cost multiplies — and you trade O(n) per evaluation for log(answer space) evaluations.

5. The Transformation

Now we make the central move of the article.
Take the textbook problem and rewrite it in formal terms:

Given a sorted array A and target x, find the smallest index i such that A[i] ≥ x.

This is the standard lower_bound formulation. Notice what is interesting about it: we are not really searching for x. We are finding the boundary in the sequence of truth values of the predicate P(i) = (A[i] ≥ x).

i:        0   1   2   3   4   5   6   7
A[i]:     1   4   7   11  13  18  22  30
P(i):     F   F   F   F   T   T   T   T
                          ↑
                       boundary

The boundary index is the answer. Once you see this, you can ask the question that breaks the whole thing open:

Does binary search require an array?

No. It requires a predicate P over an ordered domain. The predicate must be monotonic: once it becomes true, it stays true. The domain must be ordered: we need to take midpoints. Binary search finds the boundary — the smallest element of the domain at which P is true — in O(log(|domain|)) evaluations of P. That is its actual signature.

The sorted-array problem is one instance. The domain happens to be the integer interval [0, n). The predicate happens to be A[i] ≥ x. The boundary happens to be the answer to "find x." But none of these are essential. Strip them away and you can apply the same algorithm to a dozen problems that don't look like search problems at all.

Consider:

Capacity to Ship Packages in D Days. You have an array of package weights. You have to ship them all in D days using a ship with capacity k. Each day, you load the ship with the next contiguous prefix of packages whose total weight is at most k, and you ship it. The question: what is the smallest capacity k such that all packages can be shipped within D days?

This sounds like a logistics problem, not a search problem. But look at the structure. Define P(k) = "we can ship in ≤ D days at capacity k". The predicate is monotonic: if you can do it at capacity k, you can certainly do it at any larger capacity (the larger ship is never worse). The answer is the smallest k for which P is true. The domain is the integer interval [max(weights), sum(weights)] — at minimum you need a ship that holds the largest single package; at maximum you need a ship that holds everything at once. Binary search the answer.

Koko Eating Bananas. Koko has n piles of bananas, with piles[i] bananas in pile i. She eats at some integer speed s bananas per hour. Each hour she picks a pile and eats up to s bananas from it (if the pile has fewer than s left, she finishes the pile and stops for the hour). The question: what is the smallest s such that she finishes all bananas within H hours?

Same shape, different surface. The predicate is P(s) = "she finishes in ≤ H hours at speed s". Monotonic in s. Domain [1, max(piles)]. Binary search the answer. The "eating bananas" surface is irrelevant; structurally this is identical to Capacity to Ship.

Square root of n. Given a positive number n, find the largest integer x such that x² ≤ n. Define P(x) = (x² > n). Monotonic in x. Domain [0, n]. Binary search the answer. If we want more precision than integer values give, the domain becomes the real interval [0, n], the predicate stays the same, and the halving loop terminates on a numerical tolerance instead of on integer convergence. The technique works on continuous domains as readily as discrete ones.

Median of Two Sorted Arrays. You have two sorted arrays A and B, of sizes m and n. Find the median of their union in O(log(min(m, n))) time. The naive solution merges them in O(m + n) and reads the middle. The O(log) solution is genuinely different: it does not search for the median value. It searches for the median partition position. We binary search on i ∈ [0, m], where i is the number of elements from A that go to the "left half" of the merged result. Given i, the corresponding partition j of B is determined arithmetically. The predicate is "is the partition valid?" — and we'll see in Section 9c that this predicate is monotonic in i. Binary search the partition position.

The transformation is not subtle. It is a single observation: if you have a monotonic predicate over an ordered domain, you have a binary-search problem. Most of the work in any non-trivial application is figuring out what the predicate should be. The halving loop is mechanical.

The article's centerpiece. Four problems with completely different surfaces (logistics, bananas, mathematics, partition positions) flatten to the same shape: a monotonic predicate over an ordered domain, with a single F → T boundary that is the answer. The substrate varies wildly; the algorithm is identical.

6. The Pattern, Named

The technique we just derived has a name: binary search on a monotonic predicate, sometimes called parametric search or binary search on the answer. It is older than computer science — versions of it appear in mathematics as the method of bisection for finding roots of continuous functions, going back at least to the work of Cauchy in the 1820s. The variant most readers learned — find x in a sorted array — is the special case where the predicate is A[i] ≥ x over the array's index range. Every other variant is the same idea over a different domain.

The general signature:

Inputs:
  - An ordered domain D, an interval [lo, hi]
  - A monotonic predicate P : D → {false, true}
Output:
  - The boundary: the smallest x ∈ D such that P(x) is true.

The pattern's signature in problem statements:

1. "Find the smallest/largest k such that…" — almost always.
2. "Minimize the maximum…" or "Maximize the minimum…" — the answer is monotonic in the bound; binary search on the bound.
3. "What is the smallest capacity/speed/value for which the simulation succeeds?" — binary search on the parameter.
4. "Find a value x such that f(x) = 0 and f is monotonic" — root-finding; same algorithm.

The pattern is older and more general than any single problem that uses it. Section 9 walks through three more variants in depth. Section 11 lists practice problems grouped by which flavor of monotonicity they exercise.

A reference card for the pattern. The visual signature is the F → T strip with two converging pointers; the trigger phrases are the words in a problem statement that should reach you for this technique..

7. Why It Works — A Proof

The algorithm is small enough that a full proof fits on one page. Here it is.

Setup. Let D = [lo, hi] be an integer interval. Let P : D → {false, true} be a predicate satisfying:

Monotonicity. If P(a) = true and b ≥ a, then P(b) = true.

Assume the boundary exists: there is some b ∈ D with P(b) = true. (If not, the algorithm will report no solution.)

Invariant. After each iteration of the binary search loop, the two pointers lo and hi satisfy:

1. P(lo - 1) = false, OR lo is the original starting value.
2. P(hi) = true, OR hi is one past the original ending value.

That is, the boundary lies in the half-open interval [lo, hi].

Loop body. At each iteration:

mid = lo + (hi - lo) / 2     // overflow-safe midpoint
if P(mid):
    hi = mid                  // boundary is at mid or to the left
else:
    lo = mid + 1              // boundary is strictly to the right

n each case the invariant is preserved, and the gap (hi - lo) decreases by at least half (rounded down).

Termination. Since the gap halves each iteration, after at most ⌈log₂(hi - lo)⌉ + 1 iterations the gap reaches zero. At that point lo == hi, and by the invariant this common value is the boundary.

Complexity. O(log |D|) evaluations of P. If P costs T_P per evaluation, the total cost is O(T_P · log |D|). For the textbook problem, T_P = O(1) and the total cost is O(log n). For binary-search-on-the-answer problems, T_P is the cost of the predicate simulation; total cost is O(T_P · log |answer space|).

Edge cases.

1. The boundary might be the first element of D (so P(lo) = true immediately). The invariant handles this — the loop terminates with lo == hi == original lo.
2. The boundary might not exist (P = false everywhere). The loop still terminates; we detect this case by checking P(lo) after the loop. If still false, return "no solution."
3. The real-valued case: replace integer halving with floating-point halving and terminate when hi - lo < ε. Termination is guaranteed within log₂((hi - lo) / ε) iterations.

Correctness in three claims. Half a page. The proof is short enough to keep in your head, which is the point.

8. Implementation in Go

The code is the proof, translated. Here is a generic binary-search-on-monotonic-predicate, written once and reused:

// Package bsearch provides binary search over any monotonic predicate.
package bsearch

// FindBoundary returns the smallest x in [lo, hi] for which p(x) is true.
// Returns hi + 1 if no such x exists in the interval.
//
// Precondition: p must be monotonic on [lo, hi] — once p(x) becomes true
// at some x, it stays true for all larger x in the interval.
//
// Runs in O(log(hi - lo)) evaluations of p.
func FindBoundary(lo, hi int, p func(int) bool) int {
    for lo < hi {
        mid := lo + (hi-lo)/2  // overflow-safe midpoint
        if p(mid) {
            hi = mid           // boundary at mid or left
        } else {
            lo = mid + 1       // boundary strictly to the right
        }
    }
    return lo
}

Twelve lines. Generic. Reusable. Now the textbook problem becomes a one-liner:

// Search finds the index of x in a sorted array, or -1 if absent.
func Search(arr []int, x int) int {
    i := FindBoundary(0, len(arr), func(i int) bool {
        return i < len(arr) && arr[i] >= x
    })
    if i < len(arr) && arr[i] == x {
        return i
    }
    return -1
}

And Capacity to Ship Packages, the non-obvious problem, becomes:

// ShipWithinDays returns the smallest capacity needed to ship all weights in <= D days.
func ShipWithinDays(weights []int, D int) int {
    maxW, sumW := 0, 0
    for _, w := range weights {
        if w > maxW {
            maxW = w
        }
        sumW += w
    }
    // The answer is in [maxW, sumW]. Find the smallest capacity k that suffices.
    return FindBoundary(maxW, sumW, func(k int) bool {
        days, cur := 1, 0
        for _, w := range weights {
            if cur+w > k {
                days++
                cur = 0
            }
            cur += w
        }
        return days <= D
    })
}

Notice what is the same and what is different. The FindBoundary call has the identical structure in both. What changed is the predicate. In Search, the predicate is arr[i] >= x, a single O(1) comparison. In ShipWithinDays, the predicate is a simulation of the shipping process at a given capacity — O(n) per evaluation. The total cost: O(n log(sumW)). Logarithmic in the answer space, linear per predicate evaluation.

The code makes the article's refrain visible. The FindBoundary function is the loop — the typing. The closure passed to it is the predicate — the thinking. Two different problems, identical loop, completely different thinking.

Search (left) and ShipWithinDays (right). The amber-highlighted regions are the predicate bodies; everything else is identical structurally. The left predicate is one comparison; the right one is a shipping simulation. Same loop, different thinking.

9. Generalisations and Worked Examples

Three flavours of the pattern. Koko is structurally identical to Capacity to Ship. Sqrt operates on a continuous domain and terminates on a tolerance. Median binary-searches on partition positions rather than values. The substrate changes; the algorithm doesn't.

a · Koko Eating Bananas

Same shape as Capacity to Ship, different story. Given a list of banana piles piles and a deadline H hours, find the smallest eating speed s such that Koko finishes all piles in ≤ H hours. At speed s, pile p takes ⌈p/s⌉ hours.

Domain: [1, max(piles)]. Predicate: P(s) = "total hours at speed s ≤ H". Monotonic in s: faster speeds finish in less time.

func MinEatingSpeed(piles []int, H int) int {
    maxP := 0
    for _, p := range piles {
        if p > maxP {
            maxP = p
        }
    }
    return FindBoundary(1, maxP, func(s int) bool {
        hours := 0
        for _, p := range piles {
            hours += (p + s - 1) / s  // ceiling division
        }
        return hours <= H
    })
}

The only thing distinctive about this implementation is the ceiling-division trick (p + s - 1) / s, which computes ⌈p / s⌉ using only integer arithmetic. Everything else is FindBoundary with a different predicate.

When you've seen two binary-search-on-the-answer problems with the same shape and completely different stories — packages and bananas — the shape starts to feel like the actual thing being studied. The logistics flavor of the first problem and the whimsical flavour of the second are surface decoration. The thinking is identical.

b · Square Root in Floating Point

Compute √n to six decimal places of precision, with no library functions.

This is the binary search problem with the most distinctively different substrate: the domain is a continuous interval rather than an integer one. The algorithm is structurally unchanged.

Domain: the real interval 0, n. Predicate: P(x) = (x² > n). Monotonic in x. The boundary is the value where x² = n — i.e., √n.

The only adjustment for floating point: the loop terminates not when lo == hi (which may never happen for reals) but when hi - lo < ε for some tolerance ε.

// Sqrt returns sqrt(n) to within epsilon = 1e-7.
func Sqrt(n float64) float64 {
    lo, hi := 0.0, n
    if n < 1.0 {
        hi = 1.0
    }
    for hi-lo > 1e-7 {
        mid := lo + (hi-lo)/2
        if mid*mid > n {
            hi = mid
        } else {
            lo = mid
        }
    }
    return lo
}

Same algorithm. Continuous domain. The technique doesn't care whether the underlying type is int or float64. What matters is the existence of a monotonic predicate and an ordered domain. Both hold here.

The convergence is geometric in the same sense as the integer case: each iteration halves the gap. For a starting gap of n ≈ 10 and a tolerance of 10⁻⁷, we need about log₂(10 / 10⁻⁷) ≈ 27 iterations. The square root of any reasonable double-precision number converges in fewer than 50 iterations of FindBoundary, which is faster than nearly any analytical alternative.

c · Median of Two Sorted Arrays

The deep cut. Given two sorted arrays A and B (sizes m and n), find the median of their union in O(log(min(m, n))) time.

The naive approach: merge A and B in O(m + n) and read the middle. Linear time. The O(log) approach is genuinely different — and the trick is that we are not searching for the median value. We are searching for the median partition position.

Without loss of generality assume m ≤ n (swap if necessary). Define i ∈ [0, m] as a partition of A: elements A[0..i) go to the "left half" of the merged array, A[i..m) to the right half. Given i, the corresponding partition j = ⌊(m + n + 1) / 2⌋ - i is the partition of B. The merged left half consists of A[0..i) ∪ B[0..j).

For i to be the correct partition, two conditions must hold:

B[j - 1] ≤ A[i]      (left of B doesn't overflow into right of A)
A[i - 1] ≤ B[j]      (left of A doesn't overflow into right of B)

(Edge values when i = 0, i = m, j = 0, or j = n are handled by treating the missing values as ±∞.)
The crucial fact: as i increases, A[i] increases and B[j - 1] decreases (because j decreases). So the first condition — B[j - 1] ≤ A[i] — is monotonic in i: at small i it is false (B has too many elements crammed into the left half), at large i it is true. This is the False → True shape FindBoundary expects. Binary search on i ∈ [0, m] for the smallest i where B[j - 1] ≤ A[i]; the second condition is automatically satisfied at that point (because of the symmetric monotonicity of A[i - 1] and B[j]).

import "math"

// FindMedianSortedArrays returns the median of A ∪ B.
func FindMedianSortedArrays(A, B []int) float64 {
    if len(A) > len(B) {
        A, B = B, A // ensure A is the shorter
    }
    m, n := len(A), len(B)
    half := (m + n + 1) / 2

    // Binary search on i: the smallest number of A-elements in the left half
    // such that B[j-1] ≤ A[i]. (Upper bound m+1 so i=m always satisfies.)
    i := FindBoundary(0, m+1, func(i int) bool {
        j := half - i
        aRight := math.MaxInt
        if i < m {
            aRight = A[i]
        }
        bLeft := math.MinInt
        if j > 0 {
            bLeft = B[j-1]
        }
        return bLeft <= aRight
    })

    j := half - i
    var leftMax int
    switch {
    case i == 0:
        leftMax = B[j-1]
    case j == 0:
        leftMax = A[i-1]
    default:
        leftMax = max(A[i-1], B[j-1])
    }

    if (m+n)%2 == 1 {
        return float64(leftMax)
    }

    var rightMin int
    switch {
    case i == m:
        rightMin = B[j]
    case j == n:
        rightMin = A[i]
    default:
        rightMin = min(A[i], B[j])
    }
    return float64(leftMax+rightMin) / 2.0
}

The implementation is longer because of the careful index arithmetic, but the structural move is the same as everything else in the article: FindBoundary over a monotonic predicate. The substrate is no longer "an array of values" — it is the partition position, an integer in [0, m]. Once we found the right i, the median is computed from the four boundary values in constant time.

This is the article's most dramatic example of substrate change. We are still binary-searching, but the domain is not a value space — it is a position space. The pattern doesn't care.

10. Where It Shows Up in Real Systems

The interesting question isn't can you solve LeetCode 704. It is: where does binary search appear in software that ships?

Database indexes. B-tree and B+tree lookups perform binary search at every level of the tree. The predicate is key ≤ target. Every relational database on Earth does this billions of times per day. Without it, an indexed query would be O(n) on the table size instead of O(log n) — the difference between a database and a flat file.

Compilers — scheduling and register allocation. Some scheduling heuristics binary-search the answer space for "smallest schedule length that satisfies all dependency constraints" or "smallest spill cost that allows the live ranges to fit in the available registers." The predicate is a feasibility check on the rest of the compiler's machinery; the search is on the bound.

Auction systems. Many auction designs (especially second-price and Dutch auction variants) compute the clearing price by binary-searching the price domain: "at price p, does total demand meet supply?" Monotonic in p. Production ad-auction systems lean on parametric search for clearing price computations.

Rate limiters and capacity planning. "What is the largest request rate at which 99% of requests succeed?" Binary search the rate. The predicate is a load test. This is parametric search at production scale, run continuously on infrastructure dashboards.

Scientific computing. Root-finding via bisection is exactly binary search on a continuous monotonic function. Used in everything from solving Kepler's equation for orbital mechanics to inverting cumulative distribution functions in statistical computing.

Storage engines. Log-Structured Merge Trees (used in Cassandra, LevelDB, RocksDB) maintain sorted runs of data; lookups within a run are binary search. The fact that the runs are merged in the background doesn't change the per-read algorithm.

Operating systems and networking. Page tables, route tables, and address-space mappings often use binary-searchable structures. Looking up a virtual address in a sparse page table is, structurally, a binary search.

In every case the surface looks different — a database B-tree, a compiler scheduler, an auction clearing price, a numerical solver. The underlying move is identical: a monotonic predicate over an ordered domain, halved until the boundary is found.

11. Problems That Exercise This Pattern

If you want to internalize the technique, here are problems where binary search on a monotonic predicate is the right tool. They are grouped by which flavor of monotonicity they exercise, not by difficulty.

Search on a sorted array (the boring case)

1. Binary Search — the canonical problem. Boundary on A[i] ≥ x.
2. First and Last Position in a Sorted Array — two boundaries instead of one. Call FindBoundary twice.
3. Search in Rotated Sorted Array — the array is sorted modulo a rotation. The predicate is subtler: "is mid in the same sorted half as lo?"
4. Find Peak Element — predicate: A[i] > A[i + 1]. The peak is on the side where this becomes true.

Binary search on the answer

1. Capacity to Ship Packages in D Days — the canonical "search the parameter; predicate is a simulation."
2. Koko Eating Bananas — same shape, different story.
3. Split Array Largest Sum — minimize the maximum chunk size.
4. Magnetic Force Between Two Balls — maximize the minimum gap.
5. Painter's Partition — minimize the maximum painter's workload.

Continuous / floating-point binary search

1. Square Root (no library) — the canonical continuous case.
2. Pow(x, n) with fractional precision — once formulated as a root-finding problem.
3. Find Right Interval — search position in sorted starts.

Cross-domain (the technique outside its native habitat)

1. Median of Two Sorted Arrays — binary search on partition position.
2. Aggressive Cows — game-theoretic flavor; same shape as Magnetic Force.
3. Kth Smallest Element in a Sorted Matrix — binary search on value, with a 2D predicate that counts elements ≤ candidate.

A practice exercise

For each problem above, before writing any code, name aloud:

• What is the domain? — the variable you'll halve over.
• What is the predicate? — the question whose answer is monotonic.
• In which direction is it monotonic? — boundary on the left or the right?
• What does evaluating the predicate cost?
• Can the predicate be checked correctly at the boundary itself?

If you can answer these five questions in under a minute for any problem in the list, the pattern is yours.

What You Should Take Away

If you remember nothing else, remember the method.

We observed that the only structural fact binary search needs is that some predicate is monotonic over an ordered domain — not that we have a sorted array of values, though one happens to be sufficient. We decomposed binary search into two parts: the predicate (where the thinking lives) and the halving loop (which is mechanical). We read the constraint of O(log n) as a demand that we halve, which required monotonicity. We transformed "find x in a sorted array" into "find the boundary where the predicate A[i] ≥ x first becomes true" — and discovered that the predicate doesn't need to come from an array at all. The pattern that emerged — binary search on a monotonic predicate — appears across logistics, mathematics, compilers, databases, and scientific computing. And we proved correctness in three short claims: invariant, halving, termination.

That sequence — observe, decompose, read constraints, transform, recognize the pattern, prove it — is the template this series is built on. The problems change. The method does not.

Most courses teach binary search as a one-trick algorithm for sorted arrays. The arrays come first, the algorithm comes second, and the student leaves believing that binary search is for the rare moment when a sorted array drops into their lap.

But the technique is the other way around. The algorithm is general. The sorted-array case is a footnote. The interesting cases are everything else — the simulations whose feasibility is monotonic in some parameter, the continuous functions whose zeros we want to locate, the partition positions whose validity is monotonic in their offset.

The predicate is the thinking. The loop is the typing. The search came last. The search was never the point.