On this page

Binary Search Mastery

Binary search finds a boundary in a monotone sequence by halving the candidate range at every step: candidates become one in probes — 30 for a billion. Everyone "knows" it, and almost everyone writes it wrong at least once: off-by-one errors, infinite loops when the range has two elements, the wrong answer when the target repeats, an integer overflow that sat in the JDK for nine years. This lesson replaces the memorised loop with one idea that cannot go wrong — find the first index where a monotone predicate becomes true, in a half-open range — and then uses that single template for lower and upper bound, rotated arrays, peaks, "search on the answer" optimisation problems, real numbers, matrices, and finally parallel binary search over many queries at once.

Lesson position: Module 2 · Searching & Sorting · previous: Sorting in the Real World · next: Other Searches · course map.

Why this exists

A sorted array of elements can answer "where is ?" by scanning — comparisons — or by comparing with the middle element and discarding the half that cannot contain it. Each comparison removes half of what is left, so comparisons suffice, and no comparison-based method can do better in the worst case: with yes/no answers you can distinguish at most outcomes, and there are possible insertion positions. For that is 30 comparisons instead of a billion. Binary search is the reason sorting is worth paying for, the reason B-trees and SSTable indexes work, and the reason git bisect can find the commit that broke the build among 10,000 in 14 builds.

The idea is old — John Mauchly described it in 1946 in the Moore School lectures, among the first lectures on electronic computing — but correct implementations were not. Bentley, citing Knuth's The Art of Computer Programming (Vol. 3, §6.2.1), notes that while the first binary search was published in 1946, the first version that worked correctly for every did not appear until 1962. Jon Bentley reported in Programming Pearls that when he asked professional programmers to write binary search, about 90% of them had bugs. And in 2006 Joshua Bloch, who had written java.util.Arrays.binarySearch, published "Extra, Extra – Read All About It: Nearly All Binary Searches and Mergesorts are Broken" on the Google Research blog: the line int mid = (low + high) / 2; overflows when low + high exceeds , which happens for arrays of more than about a billion elements. The bug had been in the JDK for about nine years and in Bentley's own published proof-of-correctness code before that.

The lesson of that history is that binary search is not a loop to memorise but an invariant to maintain. Once you state precisely what is known about the region left of lo and the region from hi onward, every line of the loop is forced, and the same four lines solve problems that do not look like searching at all: the minimum ship capacity to deliver packages in days, the smallest eating speed that finishes in hours, the earliest day a condition holds for each of queries.

Pattern triggers

If the problem says or has…Think of…
"sorted array", "find the position / insertion point / first occurrence / last occurrence"lower_bound / upper_bound on a half-open range
"first such that…", "smallest that works", "earliest time", "first bad version"First-true on a monotone predicate
"minimise the maximum…", "maximise the minimum…" (largest sum, distance, load)Search on the answer with a greedy feasibility check
A feasibility check that is easy but the optimum is hard: "can we do it with capacity ?"The check is monotone in → binary search
Constraints like and values up to or — binary search over the value range
"rotated sorted array", "sorted then shifted"Binary search comparing against an endpoint to know which half is sorted
"peak", "local maximum", "bitonic", "mountain array"Binary search on the slope sign a[m] < a[m+1]
"precision ", continuous answer (a root, a time, a distance)Real-valued binary search with a fixed iteration count
Rows and columns sorted, "-th smallest in a matrix / in pairwise sums"Binary search on the value, count elements mid
Many queries, each "the first time at which my condition holds", updates arrive over timeParallel binary search (offline)
required, or up to with an implicit sequenceBinary search — almost nothing else is logarithmic without preprocessing

The common thread is the word monotone. Binary search does not need a sorted array; it needs a yes/no question whose answer, as a function of the index or value, goes false, false, …, false, true, true, …, true exactly once. A sorted array is just the most common source of such a predicate: "is a[i] >= x?".

Intuition & first principles

Forget "search for " for a moment. Think of a row of light switches that are all off up to some point and all on from that point. You want the first switch that is on. You check the middle one. If it is on, the first on-switch is here or to the left; if off, it is strictly to the right. Every check halves the stretch you are unsure about. That is the whole algorithm. Everything else is bookkeeping about which stretch you are unsure about.

Make it precise. Let be a predicate on the integers in that is monotone: if is true then is true for every . Then there is a unique boundary such that is false for and true for ( means "never true"). Finding is the problem.

Maintain two indices with this invariant:

  • everything in is known false,
  • everything in is known true,
  • so lies in — the closed interval, because is possible.

Start with , : nothing is known, and the invariant holds vacuously. While , test , which satisfies :

  • true: everything from on is true, so set .
  • false: everything up to and including is false, so set .

Both updates preserve the invariant and strictly shrink . When , the unknown interval has collapsed to a single point and . That's it — no == target test, no -1 return, no lo <= hi versus lo < hi agonising. The answer is always lo, and it is always meaningful: it is where the predicate turns true, which for "a[i] >= x" is the first occurrence of if present and its insertion point if not.

Why half-open? With the length is , an empty range is , the "not found" answer is a valid insertion point instead of a sentinel, and splitting at gives and with no overlap and no gap. It is the same convention as Python slices, C++ iterators and Java's subList — Dijkstra's 1982 note "Why numbering should start at zero" argues for it on exactly these grounds.

Why does mid round down? With , rounding down guarantees , so hi = mid makes progress, and , so lo = mid + 1 makes progress. If you instead write the "last false" variant with lo = mid, you must round up, or a two-element range loops forever. The first-true template avoids that trap by construction.

flowchart TD
    S["lo = L, hi = H<br/>invariant: [L, lo) false, [hi, H) true"] --> C{"lo < hi ?"}
    C -->|"no"| R["return lo<br/>first true, or H if none"]
    C -->|"yes"| M["mid = lo + (hi - lo) / 2<br/>so lo <= mid < hi"]
    M --> P{"P(mid) ?"}
    P -->|"true"| T["hi = mid<br/>mid may be the answer"]
    P -->|"false"| F["lo = mid + 1<br/>mid is not the answer"]
    T --> C
    F --> C

Mechanics

lower_bound and upper_bound

For a sorted array a and a value x:

  • lower_bound(x) = first index with a[i] >= x = number of elements . If x is present, it is its first occurrence; otherwise, where it would be inserted.
  • upper_bound(x) = first index with a[i] > x = number of elements . One past the last occurrence of x.

So upper_bound(x) - lower_bound(x) is the count of x, [lower_bound(x), upper_bound(x)) is the range of copies (C++ equal_range), and x is present iff lower_bound(x) < n and a[lower_bound(x)] == x. Both predicates are monotone because a is sorted: once a[i] >= x, every later element is at least as large.

Trace: lower_bound of 7 in [1, 3, 3, 5, 7, 7, 7, 9, 11] (indices 0–8, ; computed by script):

Iterlohimida[mid]a[mid] >= 7 ?UpdateUnknown region
start09————[0, 9]
10947truehi = 4[0, 4]
20423falselo = 3[3, 4]
33435falselo = 4[4, 4]
end44———return 4—

Notice that iteration 1 found a 7 at index 4 and did not stop: a classic search would return 4 here by luck, but it could equally have hit index 5 or 6. The first-true search keeps going until it has proved nothing earlier is true. Here, index 4 really is the first 7.

Trace: upper_bound of 7 on the same array:

Iterlohimida[mid]a[mid] > 7 ?Update
10947falselo = 5
25979truehi = 7
35767falselo = 7
end77———return 7

So 7 occurs 7 - 4 = 3 times, at indices 4, 5, 6. Other values, from the same script: lower_bound(3) = 1, upper_bound(3) = 3, lower_bound(4) = 3 (4 is absent; it would go before the 5), lower_bound(0) = 0, lower_bound(12) = 9 (past the end).

lower_bound never stops on a hit: it keeps shrinking the unknown region [lo, hi) until it is empty, so lo is proved to be the first index with a[i] ≥ x.

For comparison, here is the classic "find the exact value" search with a closed range [lo, hi] and an early exit — the version most people learn first. It is fine for "is present?" but tells you nothing useful when repeats or is absent:

The overflow bug (Bloch, 2006)

In a 32-bit int, (low + high) / 2 overflows once low + high > 2,147,483,647. With low = 1,500,000,000 and high = 2,000,000,000 the sum wraps to and mid becomes — an ArrayIndexOutOfBoundsException in Java and undefined behaviour in C/C++. The fixes:

  • mid = lo + (hi - lo) / 2 — correct whenever ; works in every language. Use this.
  • mid = (lo + hi) >>> 1 in Java — the unsigned shift treats the wrapped sum as an unsigned 32-bit value and halves it correctly (here: 1,750,000,000). This is what the JDK switched to.
  • C++20 std::midpoint(lo, hi) — overflow-free by specification.
  • Python integers do not overflow; JavaScript numbers are exact to , but (lo + hi) >> 1 in JavaScript converts to a signed 32-bit integer first, so it breaks for indices above — use Math.floor((lo + hi) / 2) or lo + ((hi - lo) >> 1).

The bug matters most not for arrays (few have elements) but for search on the answer, where lo and hi are values like or — use 64-bit types and the subtraction form there.

Rotated sorted arrays

A rotated sorted array is a sorted array cut at some point with the two pieces swapped: [4, 5, 6, 7, 0, 1, 2]. It is not sorted, but the key observation is that for any , at least one of the halves and is sorted, and you can tell which by comparing a[lo] with a[mid]: if a[lo] <= a[mid] the left half contains no rotation point and is sorted. Then check whether the target lies within that sorted half's range; if so go there, otherwise go to the other half.

Trace: search for 0 in [4, 5, 6, 7, 0, 1, 2] (closed range, since we test for equality):

lohimida[mid]Sorted halfTarget in it?Next
0637left [4..7] ()? nolo = 4
4651left [0..1] ()? yeshi = 4
4440—foundreturn 4

Finding the minimum (the rotation point) is a cleaner first-true problem: with distinct values, the predicate "a[i] <= a[n-1]" is false on the left piece and true on the right piece, so the first true index is the minimum. No target, no case analysis.

With duplicates it degrades to . Consider [1, 1, 1, 1, 1, 0, 1] and [1, 0, 1, 1, 1, 1, 1]. In both, a[lo] = a[mid] = a[hi] = 1, and nothing distinguishes whether the 0 is left or right of mid. The standard fix is to shrink by one (hi -= 1 when a[mid] == a[hi] while searching for the minimum — safe because a[hi] has a copy at mid), which is in the worst case. This is not a weakness of the algorithm but of the problem: take an array of ones and a single zero. Every rotation of [0, 1, 1, …, 1] is a valid input, so the zero can be at any of the positions, and a probe at any position other than the zero reveals only "1". An adversary answers "1" to every probe until one position is left, so any algorithm needs probes in the worst case. LeetCode 81 and 154 exist precisely to teach this.

Peak finding

A peak is an index whose value is at least its neighbours' (with beyond the ends). In an array where adjacent elements differ, compare a[mid] with a[mid + 1]: if a[mid] < a[mid + 1] the array is rising at mid, and following the rise must reach a peak before the right end (because ), so a peak exists in ; otherwise a peak exists in . This is first-true on the predicate "a[i] > a[i+1]" — not monotone over the whole array, but the invariant "there is a peak in " is maintained, which is all the proof needs. For [1, 2, 1, 3, 5, 6, 4] the search returns index 5 (value 6); index 1 is also a peak, and the problem allows either. The general lesson: binary search needs only an invariant that the halving preserves, not global sortedness.

Search on the answer

Many optimisation problems have this shape: find the smallest value such that feasible(v) holds, where feasibility is monotone — if you can do it with you can do it with anything larger. Then the answer is first-true over the range of possible values, and the cost is feasibility checks.

The monotonic-predicate argument is the step you must actually make, in words, for every such problem:

  • Koko eating bananas (piles , hours, eat at most bananas per hour from one pile): hours needed at speed are , which is non-increasing in because each term is. So "finishes within hours" is monotone in . Range: — speed finishes in hours.
  • Capacity to ship packages in days (weights in fixed order, ship daily up to capacity ): greedy loading — put packages on today's ship until the next would exceed — uses the fewest days for a given (exchange argument: any schedule can be shifted to load earlier days fuller without adding days). A larger never needs more days, since any loading for is valid for . Range: .
  • Split array largest sum (split into contiguous parts minimising the largest part sum): "can we split so every part sums to at most ?" is the same greedy and the same monotonicity; it is literally the shipping problem with .
  • Minimum days to make bouquets (flower blooms on day ; a bouquet needs adjacent bloomed flowers): the set of bloomed flowers only grows with the day, so the greedy count of bouquets on day is non-decreasing in . Range: ; impossible if .

Trace: Koko with piles [3, 6, 7, 11], , search (computed):

lohimid hours ?Update
11161+1+2+2 = 6truehi = 6
1631+2+3+4 = 10falselo = 4
4651+2+2+3 = 8truehi = 5
4541+2+2+3 = 8truehi = 4
44———answer 4

For shipping weights in days, the days needed at capacities 14, 15, 16 are 6, 5, 5, so the answer is 15; the search over probes 32, 21, 15, 12, 14 and returns 15. Split [7, 2, 5, 10, 8] into 2 parts: 18. Bouquets for bloom days [1, 10, 3, 10, 2], , : day 3.

flowchart LR
    A["Optimisation problem<br/>minimise v"] --> B["Write feasible(v)<br/>usually a greedy O(n) check"]
    B --> C{"Monotone?<br/>feasible(v) implies feasible(v+1)"}
    C -->|"no"| X["Not binary-searchable<br/>rethink: DP, ternary, ..."]
    C -->|"yes"| D["Bound the range<br/>lo = surely infeasible + 1, hi = surely feasible"]
    D --> E["first_true(lo, hi, feasible)<br/>O(n log V)"]

When the answer is a real number (a square root, the time two moving objects meet, the largest radius that fits), the same invariant works on an interval of doubles: P(lo) false, P(hi) true. Each step halves the width, so reaching width from width takes iterations: 31 for , ( by bisection), 60 for , .

Prefer a fixed iteration count — for _ in range(100) — over while hi - lo > eps. Doubles have 53 bits of precision, so near adjacent doubles are about apart. If you ask for there, hi - lo can never get that small: mid rounds to lo or hi, the interval stops shrinking, and the loop never ends. A script searching for on with was still looping after 5,000 iterations with hi - lo stuck at . One hundred halvings shrink any double interval to adjacent values, so a fixed 100 iterations is always enough and always terminates. Use a relative tolerance if you must stop early.

Binary search on sorted matrices

Two different structures, two different techniques:

  • Fully sorted rows, each row starting after the previous row ends (LeetCode 74): the matrix is a sorted array of length in row-major order. Binary search on index with element M[i // n][i % n]. .
  • Rows sorted and columns sorted (Young tableau, LeetCode 240/378): not a sorted sequence. To find a value, start at the top-right corner and step left or down — "staircase" search, not binary search. To find the -th smallest, binary search on the value with the predicate "at least elements are ", counted by the staircase in . Monotone because the count is non-decreasing in ; the first true is an actual matrix element because the count only changes at element values. Total . For [[1,5,9],[10,11,13],[12,13,15]] and the answer is 13.

The same "binary search on value, count with a linear sweep" trick finds the -th smallest pairwise distance, the -th smallest fraction, and the median of a multiplication table.

Parallel binary search (offline)

Suppose there are queries, each asking "what is the first time at which my condition holds?", where conditions depend on a sequence of updates applied in order, and each condition is monotone in (once true, stays true). Binary searching each query separately means replaying updates up to for every probe: update applications. Parallel binary search runs all binary searches simultaneously, in rounds: in each round, every unresolved query has a current and a midpoint; sort (bucket) the queries by midpoint, replay all updates once from scratch, and after applying update , evaluate every query whose midpoint is . Each round costs (update cost , check cost ), and there are rounds, so the total is — the replay is shared by all queries.

The classic example is the Polish Olympiad problem Meteors (POI 2011): a circle of sectors owned by member states, meteor showers each adding samples to a range of sectors, and each state needs a total of samples over its sectors — find the first shower after which each state has enough. With a Fenwick tree supporting range-add and point-query, it runs in .

Worked example (computed by script). Six cells owned by members [0, 1, 0, 2, 1, 2]; four updates (day: add to cells ): day 1 +2 on 0..2, day 2 +3 on 3..5, day 3 +1 on 0..5, day 4 +4 on 1..3. Needs: member 0 needs 4, member 1 needs 7, member 2 needs 6. Totals per member after each day: day 1 [4, 2, 0], day 2 [4, 5, 6], day 3 [6, 7, 8], day 4 [10, 11, 12]. Each search range is where 5 means "never".

RoundMembermid dayTotal after mid need?New range
10[1, 5)36yes (need 4)[1, 3)
11[1, 5)37yes (need 7)[1, 3)
12[1, 5)38yes (need 6)[1, 3)
20[1, 3)24yes[1, 2)
21[1, 3)25no[3, 3) — done: day 3
22[1, 3)26yes[1, 2)
30[1, 2)14yes[1, 1) — done: day 1
32[1, 2)10no[2, 2) — done: day 2

Three rounds, each replaying the four updates once, answer all three queries: days 1, 3, 2. Here is tiny, but with the difference between one replay per round and one replay per probe is the difference between seconds and hours.

Fractional cascading (a mention)

Searching for in separate sorted lists of total size costs with independent binary searches. Fractional cascading (Chazelle and Guibas, 1986) preprocesses the lists so that, after one binary search in the first list, the position in each next list is found in by following pointers from a merged sample of every second element of the following list. Total per query, extra space. It is the engine inside range trees and several computational-geometry structures (see Spatial Trees); in interviews it is enough to know it exists and what it buys.

The ladder: brute force → better → optimal

Problem: in a sorted array (with duplicates), find the first index with a[i] >= x.

Rung 1 — linear scan. Walk from the left until a[i] >= x. time, space. Correct, trivially. Wastes the sortedness entirely; for and queries it is steps.

Rung 2 — classic binary search, then walk left. Find some index with a[i] == x with the textbook lo <= hi search, then step left while a[i-1] == x. where is the number of copies — fine for distinct keys, when the array is [7, 7, …, 7]. It also needs a separate path for "not present" (insertion point) and is where most off-by-one bugs live.

Rung 3 — first-true on a half-open range (lower_bound). Search directly for the boundary of the monotone predicate a[i] >= x. probes regardless of duplicates, one code path for present and absent, no sentinel. This is optimal for comparison-based search on an unstructured sorted array.

Rung 4 — generalise the predicate. The same function with an arbitrary monotone P solves upper bound, peaks, rotated minimum, search on the answer and real-valued problems. The algorithm does not get faster; your reach does. (Below the comparison model, interpolation search gets expected on uniform keys — see Other Searches — and cache-friendly layouts make the same probes several times cheaper; see Complexity.)

RungTimeHandles duplicatesAbsent targetTypical bugs
1. Linear scanyesyesnone
2. Classic search + walk, worst slowlyseparate codeoff-by-one, early exit
3. First-true / lower_boundyesreturns insertion pointalmost none once the invariant is stated
4. Generic first-truen/areturns proving monotonicity

Correctness

Theorem (first-true)

Let be monotone on with boundary . The loop

lo, hi = L, H
while lo < hi:
    mid = lo + (hi - lo) // 2
    if P(mid): hi = mid
    else:      lo = mid + 1
return lo

terminates and returns .

Invariant. ; equivalently, is false on and true on .

Initialisation. , , and by definition of .

Maintenance. Assume the invariant and . Then since . If is true, then (all indices below are false), so setting keeps . If is false, then (all indices from on are true), so and setting keeps .

Progress. In the first case decreases by ; in the second increases by . So strictly decreases and the loop terminates.

Termination. When , the invariant gives , so .

Probe count. Let . After a "true" step the new width is ; after a "false" step it is . So the width at least halves (rounding down) each step, and the loop runs at most times. For : at most 4 probes; the trace above used 3.

lower_bound and upper_bound

For sorted a, is monotone: if and then . By the theorem, lower_bound returns the first with , and every with is . Hence equals the number of elements less than , it is the first occurrence of if is present (any occurrence has , and the first such is the boundary because all earlier elements are ), and inserting at keeps the array sorted (everything before is , everything from on is ). The same argument with shows upper_bound returns the number of elements , and inserting at that position also keeps the array sorted — after all existing copies, which is what makes "insert at upper_bound" stable.

Search on the answer

If feasible is monotone on the integer range and feasible(hi - 1) is true, the theorem returns the smallest feasible value. The work is in proving monotonicity for each problem (done above for the four classics) and in choosing bounds: lo must be a value that might be feasible but nothing smaller can be, hi a value surely feasible (or use hi + 1 as the "never" sentinel). A wrong bound does not break the loop; it returns a wrong answer, which is why the bounds deserve a sentence of justification in your solution.

Invariant: if the target is in the array, it is in . At each step, if a[lo] <= a[mid], the segment is sorted (with distinct values, a rotation point inside it would make some , and then ). If the target satisfies , it can only be in that sorted segment; otherwise it is not in and must be in . Symmetrically when the right segment is sorted. Each step removes mid and one side, so the invariant holds and the range shrinks.

Complexity

VariantTimeSpace
lower_bound / upper_bound / first-true on an array — at most probes iterative
Search on the answer over range with an check beyond the check
Real-valued, width to tolerance evaluations (cap at ~100)
Rotated array, distinct values
Rotated array with duplicates typical, worst — unavoidable
-th smallest in row/column-sorted matrix
Parallel binary search, queries, updates

Best case for first-true is still — it never exits early, by design. The classic equality search can exit after one probe, which is irrelevant in practice.

Constants and cache behaviour. Each probe is a dependent load: the next address depends on the result of this comparison. On an array larger than the CPU caches, the first several probes are cache misses (about 100 ns each from DRAM), so a binary search over 4-byte integers costs on the order of 1–2 μs — dominated by ~10–15 misses, not 27 comparisons. Two well-studied fixes (Khuong and Morin, "Array Layouts for Comparison-Based Searching", 2017): the Eytzinger layout stores the implicit binary search tree in BFS order (node has children and , exactly like a binary heap), so the next few probes share cache lines and can be prefetched; and B-tree layouts put keys per cache line. Branchless binary search (replace the if with a conditional move) avoids the 50% branch misprediction rate. These are why database indexes are B-trees rather than sorted arrays — see Indexing Deep Dive.

Implementation

The canonical implementation is a generic first_true(lo, hi, pred) and four uses of it: lower_bound, upper_bound, minimum eating speed (Koko) and minimum ship capacity. The tests include a range near that breaks the (lo + hi) / 2 form in 32-bit languages.

from typing import Callable


def first_true(lo: int, hi: int, pred: Callable[[int], bool]) -> int:
    """Smallest x in [lo, hi) with pred(x) true; hi if none. pred must be monotone."""
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if pred(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo


def lower_bound(a: list[int], x: int) -> int:
    return first_true(0, len(a), lambda i: a[i] >= x)


def upper_bound(a: list[int], x: int) -> int:
    return first_true(0, len(a), lambda i: a[i] > x)


def min_eating_speed(piles: list[int], h: int) -> int:
    hours = lambda k: sum((p + k - 1) // k for p in piles)
    return first_true(1, max(piles) + 1, lambda k: hours(k) <= h)


def ship_within_days(weights: list[int], days: int) -> int:
    def days_needed(cap: int) -> int:
        d, load = 1, 0
        for w in weights:
            if load + w > cap:
                d, load = d + 1, 0
            load += w
        return d
    return first_true(max(weights), sum(weights) + 1, lambda c: days_needed(c) <= days)


if __name__ == "__main__":
    a = [1, 3, 3, 5, 7, 7, 7, 9, 11]
    assert lower_bound(a, 7) == 4 and upper_bound(a, 7) == 7
    assert lower_bound(a, 3) == 1 and upper_bound(a, 3) == 3
    assert lower_bound(a, 4) == 3 and lower_bound(a, 0) == 0 and lower_bound(a, 12) == 9
    assert lower_bound([], 5) == 0 and upper_bound([], 5) == 0
    assert first_true(0, 2_147_483_647, lambda x: x >= 2_000_000_000) == 2_000_000_000
    assert first_true(0, 10, lambda x: False) == 10
    assert min_eating_speed([3, 6, 7, 11], 8) == 4
    assert min_eating_speed([30, 11, 23, 4, 20], 5) == 30
    assert min_eating_speed([30, 11, 23, 4, 20], 6) == 23
    assert ship_within_days(list(range(1, 11)), 5) == 15
    assert ship_within_days([3, 2, 2, 4, 1, 4], 3) == 6
    assert ship_within_days([1, 2, 3, 1, 1], 4) == 3
    print("ok")
import java.util.function.IntPredicate;

public class BinarySearchMastery {
    /** Smallest x in [lo, hi) with pred(x) true; hi if none. pred must be monotone. */
    static int firstTrue(int lo, int hi, IntPredicate pred) {
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;      // never (lo + hi) / 2: overflows past 2^31 - 1
            if (pred.test(mid)) hi = mid;
            else lo = mid + 1;
        }
        return lo;
    }

    static int lowerBound(int[] a, int x) { return firstTrue(0, a.length, i -> a[i] >= x); }

    static int upperBound(int[] a, int x) { return firstTrue(0, a.length, i -> a[i] > x); }

    static int minEatingSpeed(int[] piles, int h) {
        int max = 0;
        for (int p : piles) max = Math.max(max, p);
        return firstTrue(1, max + 1, k -> {
            long hours = 0;
            for (int p : piles) hours += (p + (long) k - 1) / k;
            return hours <= h;
        });
    }

    static int shipWithinDays(int[] weights, int days) {
        int max = 0, sum = 0;
        for (int w : weights) { max = Math.max(max, w); sum += w; }
        return firstTrue(max, sum + 1, cap -> {
            int d = 1, load = 0;
            for (int w : weights) {
                if (load + w > cap) { d++; load = 0; }
                load += w;
            }
            return d <= days;
        });
    }

    static void check(boolean ok, String what) {
        if (!ok) throw new AssertionError(what);
    }

    public static void main(String[] args) {
        int[] a = {1, 3, 3, 5, 7, 7, 7, 9, 11};
        check(lowerBound(a, 7) == 4 && upperBound(a, 7) == 7, "bounds of 7");
        check(lowerBound(a, 3) == 1 && upperBound(a, 3) == 3, "bounds of 3");
        check(lowerBound(a, 4) == 3 && lowerBound(a, 0) == 0 && lowerBound(a, 12) == 9, "absent");
        check(lowerBound(new int[0], 5) == 0 && upperBound(new int[0], 5) == 0, "empty");
        check(firstTrue(0, Integer.MAX_VALUE, x -> x >= 2_000_000_000) == 2_000_000_000, "overflow range");
        check(firstTrue(0, 10, x -> false) == 10, "never true");
        check(minEatingSpeed(new int[]{3, 6, 7, 11}, 8) == 4, "koko 1");
        check(minEatingSpeed(new int[]{30, 11, 23, 4, 20}, 5) == 30, "koko 2");
        check(minEatingSpeed(new int[]{30, 11, 23, 4, 20}, 6) == 23, "koko 3");
        check(shipWithinDays(new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, 5) == 15, "ship 1");
        check(shipWithinDays(new int[]{3, 2, 2, 4, 1, 4}, 3) == 6, "ship 2");
        check(shipWithinDays(new int[]{1, 2, 3, 1, 1}, 4) == 3, "ship 3");
        System.out.println("ok");
    }
}
#include <algorithm>
#include <cassert>
#include <climits>
#include <cstdint>
#include <iostream>
#include <vector>

// Smallest x in [lo, hi) with pred(x) true; hi if none. pred must be monotone.
template <class Pred>
std::int64_t first_true(std::int64_t lo, std::int64_t hi, Pred pred) {
    while (lo < hi) {
        std::int64_t mid = lo + (hi - lo) / 2;
        if (pred(mid)) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}

std::int64_t lower_bound_idx(const std::vector<int>& a, int x) {
    return first_true(0, static_cast<std::int64_t>(a.size()), [&](std::int64_t i) { return a[i] >= x; });
}

std::int64_t upper_bound_idx(const std::vector<int>& a, int x) {
    return first_true(0, static_cast<std::int64_t>(a.size()), [&](std::int64_t i) { return a[i] > x; });
}

std::int64_t min_eating_speed(const std::vector<int>& piles, std::int64_t h) {
    int mx = *std::max_element(piles.begin(), piles.end());
    return first_true(1, mx + 1, [&](std::int64_t k) {
        std::int64_t hours = 0;
        for (int p : piles) hours += (p + k - 1) / k;
        return hours <= h;
    });
}

std::int64_t ship_within_days(const std::vector<int>& weights, int days) {
    std::int64_t mx = 0, sum = 0;
    for (int w : weights) { mx = std::max<std::int64_t>(mx, w); sum += w; }
    return first_true(mx, sum + 1, [&](std::int64_t cap) {
        int d = 1;
        std::int64_t load = 0;
        for (int w : weights) {
            if (load + w > cap) { ++d; load = 0; }
            load += w;
        }
        return d <= days;
    });
}

int main() {
    std::vector<int> a{1, 3, 3, 5, 7, 7, 7, 9, 11};
    assert(lower_bound_idx(a, 7) == 4 && upper_bound_idx(a, 7) == 7);
    assert(lower_bound_idx(a, 3) == 1 && upper_bound_idx(a, 3) == 3);
    assert(lower_bound_idx(a, 4) == 3 && lower_bound_idx(a, 0) == 0 && lower_bound_idx(a, 12) == 9);
    assert(lower_bound_idx({}, 5) == 0 && upper_bound_idx({}, 5) == 0);
    // agrees with the standard library
    assert(lower_bound_idx(a, 7) == std::lower_bound(a.begin(), a.end(), 7) - a.begin());
    assert(upper_bound_idx(a, 7) == std::upper_bound(a.begin(), a.end(), 7) - a.begin());
    assert(first_true(0, INT_MAX, [](std::int64_t x) { return x >= 2000000000; }) == 2000000000);
    assert(first_true(0, 10, [](std::int64_t) { return false; }) == 10);
    assert(min_eating_speed({3, 6, 7, 11}, 8) == 4);
    assert(min_eating_speed({30, 11, 23, 4, 20}, 5) == 30);
    assert(min_eating_speed({30, 11, 23, 4, 20}, 6) == 23);
    assert(ship_within_days({1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, 5) == 15);
    assert(ship_within_days({3, 2, 2, 4, 1, 4}, 3) == 6);
    assert(ship_within_days({1, 2, 3, 1, 1}, 4) == 3);
    std::cout << "ok\n";
}
/** Smallest x in [lo, hi) with pred(x) true; hi if none. pred must be monotone. */
function firstTrue(lo: number, hi: number, pred: (x: number) => boolean): number {
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2); // not (lo + hi) >> 1: that truncates to int32
    if (pred(mid)) hi = mid;
    else lo = mid + 1;
  }
  return lo;
}

const lowerBound = (a: number[], x: number) => firstTrue(0, a.length, (i) => a[i] >= x);
const upperBound = (a: number[], x: number) => firstTrue(0, a.length, (i) => a[i] > x);

function minEatingSpeed(piles: number[], h: number): number {
  const hours = (k: number) => piles.reduce((s, p) => s + Math.ceil(p / k), 0);
  return firstTrue(1, Math.max(...piles) + 1, (k) => hours(k) <= h);
}

function shipWithinDays(weights: number[], days: number): number {
  const daysNeeded = (cap: number) => {
    let d = 1, load = 0;
    for (const w of weights) {
      if (load + w > cap) { d++; load = 0; }
      load += w;
    }
    return d;
  };
  const sum = weights.reduce((s, w) => s + w, 0);
  return firstTrue(Math.max(...weights), sum + 1, (c) => daysNeeded(c) <= days);
}

function assert(cond: boolean, what: string): void {
  if (!cond) throw new Error("assertion failed: " + what);
}

const a = [1, 3, 3, 5, 7, 7, 7, 9, 11];
assert(lowerBound(a, 7) === 4 && upperBound(a, 7) === 7, "bounds of 7");
assert(lowerBound(a, 3) === 1 && upperBound(a, 3) === 3, "bounds of 3");
assert(lowerBound(a, 4) === 3 && lowerBound(a, 0) === 0 && lowerBound(a, 12) === 9, "absent");
assert(lowerBound([], 5) === 0 && upperBound([], 5) === 0, "empty");
assert(firstTrue(0, 2_147_483_647, (x) => x >= 2_000_000_000) === 2_000_000_000, "overflow range");
assert(firstTrue(0, 10, () => false) === 10, "never true");
assert(minEatingSpeed([3, 6, 7, 11], 8) === 4, "koko 1");
assert(minEatingSpeed([30, 11, 23, 4, 20], 5) === 30, "koko 2");
assert(minEatingSpeed([30, 11, 23, 4, 20], 6) === 23, "koko 3");
assert(shipWithinDays([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 5) === 15, "ship 1");
assert(shipWithinDays([3, 2, 2, 4, 1, 4], 3) === 6, "ship 2");
assert(shipWithinDays([1, 2, 3, 1, 1], 4) === 3, "ship 3");
console.log("ok");

All in one runnable Python block; each function is short enough to port directly.

import math


def search_rotated(a: list[int], t: int) -> int:
    """Distinct values. Closed range because we test equality."""
    lo, hi = 0, len(a) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if a[mid] == t:
            return mid
        if a[lo] <= a[mid]:                      # left half sorted
            if a[lo] <= t < a[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:                                    # right half sorted
            if a[mid] < t <= a[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1


def find_min_rotated(a: list[int]) -> int:
    """Works with duplicates; O(log n) typical, O(n) worst case (unavoidable)."""
    lo, hi = 0, len(a) - 1
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if a[mid] > a[hi]:
            lo = mid + 1                         # minimum is right of mid
        elif a[mid] < a[hi]:
            hi = mid                             # minimum is at mid or left
        else:
            hi -= 1                              # a[hi] has a copy at mid: safe to drop
    return a[lo]


def find_peak(a: list[int]) -> int:
    lo, hi = 0, len(a) - 1
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if a[mid] < a[mid + 1]:
            lo = mid + 1
        else:
            hi = mid
    return lo


def real_sqrt(x: float) -> float:
    lo, hi = 0.0, max(1.0, x)
    for _ in range(100):                         # fixed count: always terminates
        mid = (lo + hi) / 2
        if mid * mid >= x:
            hi = mid
        else:
            lo = mid
    return hi


def kth_smallest_matrix(m: list[list[int]], k: int) -> int:
    n = len(m)

    def count_le(v: int) -> int:                # staircase from the top-right, O(n)
        c, j = 0, n - 1
        for i in range(n):
            while j >= 0 and m[i][j] > v:
                j -= 1
            c += j + 1
        return c

    lo, hi = m[0][0], m[-1][-1]
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if count_le(mid) >= k:
            hi = mid
        else:
            lo = mid + 1
    return lo


def parallel_binary_search(owner, need, updates):
    """First day (1-based) each member's total reaches need; len(updates)+1 if never."""
    n, q, T = len(owner), len(need), len(updates)
    lo, hi = [1] * q, [T + 1] * q
    rounds = 0
    while any(lo[i] < hi[i] for i in range(q)):
        rounds += 1
        at_day: dict[int, list[int]] = {}
        for i in range(q):
            if lo[i] < hi[i]:
                at_day.setdefault((lo[i] + hi[i]) // 2, []).append(i)
        cells = [0] * n                          # replay all updates once per round
        for day, (l, r, x) in enumerate(updates, start=1):
            for c in range(l, r + 1):            # a Fenwick tree makes this O(log n)
                cells[c] += x
            for i in at_day.get(day, []):
                total = sum(cells[c] for c in range(n) if owner[c] == i)
                if total >= need[i]:
                    hi[i] = day
                else:
                    lo[i] = day + 1
    return lo, rounds


assert search_rotated([4, 5, 6, 7, 0, 1, 2], 0) == 4
assert search_rotated([4, 5, 6, 7, 0, 1, 2], 3) == -1
assert search_rotated([1], 1) == 0 and search_rotated([], 1) == -1
assert find_min_rotated([3, 4, 5, 1, 2]) == 1
assert find_min_rotated([2, 2, 2, 0, 1]) == 0
assert find_min_rotated([1, 1, 1, 1, 1, 0, 1]) == 0 and find_min_rotated([1, 0, 1, 1, 1, 1, 1]) == 0
assert find_peak([1, 2, 3, 1]) == 2 and find_peak([1, 2, 1, 3, 5, 6, 4]) == 5
assert real_sqrt(2.0) == math.sqrt(2.0)
assert abs(real_sqrt(2e17) - math.sqrt(2e17)) < 1e-6
assert kth_smallest_matrix([[1, 5, 9], [10, 11, 13], [12, 13, 15]], 8) == 13
answers, rounds = parallel_binary_search(
    owner=[0, 1, 0, 2, 1, 2], need=[4, 7, 6],
    updates=[(0, 2, 2), (3, 5, 3), (0, 5, 1), (1, 3, 4)])
assert answers == [1, 3, 2] and rounds == 3
print("ok")

Library functions

Know what your language gives you, and exactly what it returns:

LanguageLower boundUpper boundExact searchGeneric first-true
Pythonbisect.bisect_left(a, x)bisect.bisect_right(a, x)i = bisect_left(a, x); i < len(a) and a[i] == xbisect_left(range(lo, hi), True, key=pred) + lo (key= since 3.10)
Javanone built innone built inArrays.binarySearch(a, x), Collections.binarySearch(list, x)write it
C++std::lower_bound(first, last, x)std::upper_boundstd::binary_search (bool), std::equal_rangestd::partition_point(first, last, not_pred) (C++11)
Rustpartition_point with predicate y < xpartition_point with y <= xbinary_search(&x) → Ok(i) or Err(insert_pos)partition_point
Gosort.SearchInts(a, x)sort.Search(n, func(i) bool { return a[i] > x })slices.BinarySearch(a, x) → (pos, found)sort.Search(n, f) — exactly first-true
JavaScriptnone built innone built innone (indexOf is linear)write it

Java's return encoding. Arrays.binarySearch returns the index of some matching element if found — not necessarily the first when there are duplicates — and otherwise -(insertionPoint) - 1. The -1 offset exists so that "not found, insert at 0" (−1) is distinguishable from "found at 0" (0). Recover the insertion point with -(r + 1) or ~r. Searching {1, 3, 3, 5} for 4 returns -4 (insertion point 3).

C++'s partition_point takes a predicate that is true on a prefix and returns the first element where it is false — the mirror image of first-true. std::lower_bound(first, last, x) is partition_point(first, last, [&](auto& y) { return y < x; }). The std::ranges versions accept projections: std::ranges::lower_bound(people, 30, {}, &Person::age).

Real-world uses

git bisect. Given a known-good and a known-bad commit, git bisect checks out the midpoint of the commit range, you (or git bisect run ./test.sh) mark it good or bad, and it halves again. "Is this commit bad?" is a monotone predicate over history (assuming the bug, once introduced, stays), so 10,000 commits need about 14 test runs. The same idea appears as "bisecting" compiler flags, optimisation passes (LLVM's opt-bisect-limit), configuration changes, and dependency versions.

Database indexes. Inside every B-tree page, keys are sorted, and the database finds the child pointer or the row with a binary search over the page's key array (often a few hundred keys). PostgreSQL's _bt_binsrch and InnoDB's page directory search are binary searches; the tree structure is what keeps the number of pages touched at three or four. See Indexing Deep Dive and How Databases Work.

LSM trees and log storage. An SSTable (RocksDB, LevelDB, Cassandra) ends with a sparse index of the first key of each data block; a lookup binary-searches that index, then the block's restart points. Kafka locates a message by offset by binary-searching its sparse offset index files and then scanning a small region of the log segment. See Storage Engines and Build a Key-Value Store.

Consistent hashing. A hash ring is a sorted array of virtual-node positions; routing a key means finding the first position , wrapping around — a lower_bound. See Consistent Hashing.

Numerics and systems tuning. Bisection is the most robust root-finding method — guaranteed convergence for any continuous function with a sign change — and is the fallback inside Brent's method (SciPy's brentq). Engineers "binary search" capacity all the time: the largest batch size that fits in GPU memory, the highest request rate a service sustains under its latency SLO, the smallest work_mem that avoids a spill. Each is search on the answer with an expensive, monotone feasibility test.

Standard library containers. C++ std::flat_map (C++23) and sorted std::vectors look up with lower_bound; Python's bisect.insort maintains sorted lists; Unicode property tables in ICU and in language runtimes are commonly stored as sorted range arrays searched by binary search.

Pitfalls & edge cases

  • (lo + hi) / 2 overflow in Java, C, C++, C#, Go — use lo + (hi - lo) / 2. In JavaScript, (lo + hi) >> 1 truncates to 32 bits; use Math.floor.
  • Infinite loop on two elements. lo = mid with mid rounded down never progresses when hi = lo + 1. Either use the first-true template (lo = mid + 1), or round up when you assign lo = mid.
  • Mixing conventions. hi = len(a) with while lo <= hi reads a[len(a)]; hi = len(a) - 1 with while lo < hi misses the last element or the "past the end" answer. Pick half-open + lo < hi + hi = mid and never mix.
  • Using the result without checking. lower_bound returns an insertion point. Before reading a[i], check i < len(a); before claiming "found", check a[i] == x.
  • Non-monotone predicate. "Sum of window of size " over is monotone only with non-negative numbers; "can finish with capacity " is monotone only if the check is greedy-optimal. If you cannot write the one-sentence monotonicity proof, the search may silently return garbage.
  • Wrong search bounds for search on the answer. Koko's lower bound is 1, not 0 (division by zero); shipping's lower bound is , not 1 (a package heavier than the capacity never ships, and the greedy check loops or miscounts); the upper bound must be surely feasible.
  • Overflow inside the check. Summing hours or loads in 32 bits when exceeds . Use 64-bit accumulators (the Java and C++ code above do).
  • Floating-point termination. while hi - lo > 1e-9 may never end for large magnitudes; use a fixed iteration count or relative tolerance.
  • Duplicates. "Find the index of " is ambiguous with duplicates; interviewers mean first or last occurrence — lower_bound or upper_bound − 1. Java's binarySearch returns an arbitrary one.
  • Searching an unsorted or wrongly sorted array. Binary search on data sorted by a different comparator (case-insensitive sort, then case-sensitive search; locale collation vs bytes) fails silently.
  • Empty input. First-true returns lo = hi = 0; the classic closed-range search with hi = -1 must not index a[0].

Variations

  • Ternary search and golden-section search — find the extremum of a unimodal function; see Other Searches.
  • Exponential (galloping) search — find the range first when is unknown or the target is near the start, ; used in Timsort. Same page.
  • Interpolation search — guess the position from the key's value; expected on uniform data, worst. Same page.
  • Binary search trees — the same halving, materialised as a data structure that supports insertion; see Binary Search Trees.
  • Binary lifting — "binary search by building the answer bit by bit from the top": jump steps if the predicate still holds. Used on Fenwick trees (find the first prefix sum in ) and in LCA & Binary Lifting.
  • Bisection on a DP or greedy ("Aliens trick" / Lagrangian relaxation) — binary search a penalty so that an unconstrained optimum uses exactly items; advanced, appears in Module 6-level DP.
  • Quickselect — not binary search, but the same "discard the half that cannot contain the answer" logic on an unsorted array; see Quickselect & Order Statistics.

Practice ladder

Easy → hard. Descriptions are paraphrased; follow the links for exact statements.

1. Binary Search (LeetCode 704) — return the index of a target in a sorted array of distinct values, or −1. Teaches the template; solve it with lower_bound plus a check.

Hint

i = lower_bound(a, t); return i if i < n and a[i] == t else -1.

2. Search Insert Position (LeetCode 35) — index of the target or where it would be inserted. Teaches that lower_bound is the insertion point.

Hint

It is exactly lower_bound. No special cases.

3. First Bad Version (LeetCode 278) — versions become bad from some point on; find the first with few API calls. Teaches first-true on a predicate with no array, and the overflow bug (the range goes up to ).

Hint

first_true(1, n + 1, isBadVersion); in Java/C++ use lo + (hi - lo) / 2.

4. Find First and Last Position of Element in Sorted Array (LeetCode 34) — the range of a target's copies. Teaches lower_bound and upper_bound together.

Hint

[lower_bound(t), upper_bound(t) - 1] if the first is in range and equals t.

Solution
from bisect import bisect_left, bisect_right


def search_range(nums: list[int], target: int) -> list[int]:
    lo = bisect_left(nums, target)
    if lo == len(nums) or nums[lo] != target:
        return [-1, -1]
    return [lo, bisect_right(nums, target) - 1]


assert search_range([5, 7, 7, 8, 8, 10], 8) == [3, 4]
assert search_range([5, 7, 7, 8, 8, 10], 6) == [-1, -1]
assert search_range([], 0) == [-1, -1]
assert search_range([1, 3, 3, 5, 7, 7, 7, 9, 11], 7) == [4, 6]
print("ok")

time, space — two binary searches regardless of how many copies exist.

5. Sqrt(x) (LeetCode 69) — integer square root without library calls. Teaches "last true" via "first true minus one" and overflow in mid * mid.

Hint

First with , minus 1. Compare mid > x // mid to avoid overflow in 32-bit languages.

6. Find Peak Element (LeetCode 162) — any index greater than its neighbours, in . Teaches binary search on an invariant rather than on sortedness.

Hint

If a[mid] < a[mid + 1], a peak exists to the right; otherwise at mid or to the left.

7. Search in Rotated Sorted Array (LeetCode 33) — find a target in a rotated array of distinct values. Teaches "one half is always sorted".

Hint

Compare a[lo] and a[mid] to find the sorted half, then check whether the target lies within its range.

Solution
def search(nums: list[int], target: int) -> int:
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if nums[mid] == target:
            return mid
        if nums[lo] <= nums[mid]:
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1


assert search([4, 5, 6, 7, 0, 1, 2], 0) == 4
assert search([4, 5, 6, 7, 0, 1, 2], 3) == -1
assert search([1], 0) == -1
assert search([3, 1], 1) == 1
print("ok")

time, space. The <= in nums[lo] <= nums[mid] matters when lo == mid (two-element ranges): [3, 1] searching for 1 fails with <.

8. Find Minimum in Rotated Sorted Array II (LeetCode 154) — the minimum when duplicates are allowed. Teaches why the worst case becomes and the safe hi -= 1 step. (Its sibling Search in Rotated Sorted Array II (LeetCode 81) has the same lesson.)

Hint

Compare a[mid] with a[hi]: greater → go right; smaller → hi = mid; equal → hi -= 1.

9. Koko Eating Bananas (LeetCode 875) — minimum eating speed to finish within hours. Teaches search on the answer and the monotonicity argument.

Hint

first_true(1, max(piles) + 1, lambda k: sum(ceil(p / k)) <= h).

10. Capacity To Ship Packages Within D Days (LeetCode 1011) — minimum ship capacity for in-order delivery in days. Teaches greedy feasibility + binary search, with careful bounds.

Hint

Range ; greedy day count; first capacity with days .

Solution
def ship_within_days(weights: list[int], days: int) -> int:
    def fits(cap: int) -> bool:
        d, load = 1, 0
        for w in weights:
            if load + w > cap:
                d, load = d + 1, 0
            load += w
        return d <= days

    lo, hi = max(weights), sum(weights)        # hi is always feasible
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if fits(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo


assert ship_within_days([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 5) == 15
assert ship_within_days([3, 2, 2, 4, 1, 4], 3) == 6
assert ship_within_days([1, 2, 3, 1, 1], 4) == 3
assert ship_within_days([10], 1) == 10
print("ok")

time, space. Starting lo at max(weights) is not an optimisation — with a smaller capacity the greedy would try to put an oversized package on an empty ship and count days wrongly.

11. Minimum Number of Days to Make m Bouquets (LeetCode 1482) — earliest day you can make bouquets of adjacent bloomed flowers. Teaches search on the answer over days, plus the impossibility check.

Hint

If m * k > n return −1. Otherwise binary search the day in [min(b), max(b)]; count bouquets with a run counter that resets on an unbloomed flower.

12. Split Array Largest Sum (LeetCode 410) — split into contiguous parts minimising the largest sum. Teaches recognising the same problem as LeetCode 1011 in disguise (and that a DP also exists, at ).

Hint

"Can every part be at most using at most parts?" is monotone in ; greedy check; range .

13. Factory Machines (CSES 1620) — machines take seconds per product; minimum time to make products. Teaches search on the answer with 64-bit overflow in the check (the answer can reach ).

Hint

Products in time are ; stop summing once it reaches to avoid overflow. Upper bound: .

14. Kth Smallest Element in a Sorted Matrix (LeetCode 378) — rows and columns sorted; -th smallest overall. Teaches binary search on the value with a staircase count.

Hint

Predicate: "at least elements are ". Count from the top-right corner in .

15. Median of Two Sorted Arrays (LeetCode 4) — the median of the union in . Teaches binary search on a partition position with a two-sided invariant.

Hint

Binary search how many elements of the shorter array go into the left half; then from the other. The partition is right when A[i-1] <= B[j] and B[j-1] <= A[i]; "A[i-1] > B[j]" is monotone in .

Solution
def find_median_sorted_arrays(a: list[int], b: list[int]) -> float:
    if len(a) > len(b):
        a, b = b, a
    m, n = len(a), len(b)
    half = (m + n + 1) // 2
    neg, pos = float("-inf"), float("inf")
    # first i in [0, m] such that a[i] >= b[half - i - 1]  (i.e. we have not taken too few from a)
    lo, hi = 0, m
    while lo < hi:
        i = lo + (hi - lo) // 2
        if a[i] >= b[half - i - 1]:
            hi = i
        else:
            lo = i + 1
    i, j = lo, half - lo
    left_max = max(a[i - 1] if i > 0 else neg, b[j - 1] if j > 0 else neg)
    if (m + n) % 2:
        return float(left_max)
    right_min = min(a[i] if i < m else pos, b[j] if j < n else pos)
    return (left_max + right_min) / 2


assert find_median_sorted_arrays([1, 3], [2]) == 2.0
assert find_median_sorted_arrays([1, 2], [3, 4]) == 2.5
assert find_median_sorted_arrays([], [1]) == 1.0
assert find_median_sorted_arrays([2], []) == 2.0
assert find_median_sorted_arrays([1, 2, 3, 4, 5], [6, 7, 8]) == 4.5
assert find_median_sorted_arrays([4, 5, 6], [1, 2, 3]) == 3.5
print("ok")

time, space. Written as first-true: the predicate "a[i] >= b[half-i-1]" is monotone in because the left side grows and the right side shrinks as increases; the boundary is the unique valid partition.

Common mistakes & interview follow-ups

"Your array has duplicates — which index do you return?" Ask whether they want first or last; return lower_bound or upper_bound - 1. Pointing out that classic binary search returns an arbitrary copy shows you have thought about it.

"What if the array is too large to fit in memory / is on disk?" Binary search still needs only reads, but each is a random I/O. Use a sparse in-memory index (every -th key) to find the right block, then search inside it — this is exactly an SSTable index or a B-tree.

"What if you don't know (an infinite or streamed sorted array)?" Exponential search: probe indices 1, 2, 4, 8, … until you pass the target, then binary search the last gap. where is the target's position. See Other Searches.

"Prove the feasibility check is monotone." Give the one-sentence argument: any solution for a smaller capacity/speed/day is also a solution for a larger one. If the interviewer pushes, give the exchange argument that the greedy check is optimal.

"What's the overflow bug?" (lo + hi) / 2 exceeds INT_MAX for large indices; use lo + (hi - lo) / 2. Mention Bloch's 2006 post and that it was in the JDK for years.

"Recursive or iterative?" Iterative: space, no stack depth concerns, and the invariant is easier to see. Recursion depth is only , so either is acceptable, but iterative is the default.

"Can binary search work on a linked list?" Not in — finding the middle costs , so the total is (with comparisons, which matters only if comparisons are expensive). Skip lists exist precisely to give linked structures logarithmic search.

"Many queries, each binary searching over time, with updates?" Parallel binary search: rounds, each replaying updates once. Or a persistent data structure, which answers online.

Quick quiz

1. In the first-true template, why is it safe to set hi = mid (not mid - 1) and necessary to set lo = mid + 1 (not mid)?

Answer

When P(mid) is true, mid itself might be the first true index, so it must stay in the candidate range — hi = mid keeps it. When P(mid) is false, mid is definitely not the answer, so lo = mid + 1 excludes it; lo = mid would also fail to make progress when mid == lo, causing an infinite loop on two-element ranges.

2. For a = [2, 4, 4, 4, 8], what are lower_bound(4), upper_bound(4), lower_bound(5) and upper_bound(9)? What does Java's Arrays.binarySearch(a, 5) return?

Answer

1, 4, 4, 5. binarySearch(a, 5) returns -(4) - 1 = -5, since 5 would be inserted at index 4.

3. Why does searching a rotated sorted array with duplicates take in the worst case for any algorithm?

Answer

With ones and one zero, every rotation is a valid input, so the zero can be at any position. A probe anywhere except the zero returns 1 and gives no information about where the zero is (all remaining positions are still consistent). An adversary can therefore force probes.

4. You binary search a real answer on with while hi - lo > 1e-9. What can go wrong, and what should you write instead?

Answer

Near adjacent doubles are about apart, so hi - lo can never drop below : mid rounds to lo or hi and the loop runs forever. Use a fixed number of iterations (100 is always enough for doubles) or a relative tolerance.

5. In parallel binary search with queries and updates, why is the total cost update/check operations rather than ?

Answer

Each round replays all updates once and checks each unresolved query once at its midpoint, costing operations. Every query's range halves each round, so there are rounds. Separate binary searches would replay up to updates for every probe of every query.

Further reading / sources

  • Donald E. Knuth, The Art of Computer Programming, Vol. 3, 2nd ed., §6.2.1 "Searching an Ordered Table" — history of the method, uniform binary search, and exact probe counts.
  • Jon Bentley, Programming Pearls, 2nd ed., Column 4 "Writing Correct Programs" — the binary search exercise and loop-invariant reasoning.
  • Joshua Bloch, "Extra, Extra – Read All About It: Nearly All Binary Searches and Mergesorts are Broken", Google Research Blog, June 2006.
  • Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms, 4th ed. — Chapter 2 (loop invariants; binary search appears in the exercises).
  • cp-algorithms, Binary search — including search on the answer and real-valued search.
  • Bernard Chazelle and Leonidas J. Guibas, "Fractional Cascading: I. A Data Structuring Technique", Algorithmica 1, 1986.
  • Paul-Virak Khuong and Pat Morin, "Array Layouts for Comparison-Based Searching", ACM Journal of Experimental Algorithmics 22, 2017 (arXiv:1509.05053).
  • Edsger W. Dijkstra, "Why numbering should start at zero" (EWD831), 1982 — the case for half-open ranges.
  • Python bisect documentation; Java Arrays.binarySearch Javadoc; C++ std::lower_bound / std::partition_point on cppreference.

Lessons: previous — Sorting in the Real World · next — Other Searches · module — Searching & Sorting · course map.

Related Archon pages: Sorting & Searching overview · Quickselect & Order Statistics · Binary Search Trees · Fenwick Trees · Indexing Deep Dive · Consistent Hashing · Two Pointers · Testing & Debugging Algorithms.