Binary search algorithm

Binary search is the first non-trivial algorithm most engineers learn, and it is usually taught as look up a value in a sorted array. That is the smaller half of what it does here. In the problems below it does two quite different jobs: it finds a value in a sorted array, and — more often, and more decisively — it finds the answer itself, by halving an interval of candidate answers against a monotone test. The second use is the one that turns a search over $10^9$ candidates into forty evaluations of a formula, and it needs no array at all.

The idea — the invariant, not the loop

The loop is six lines and everybody can write it. What actually needs care is the invariant, and stating it explicitly is the difference between a search that is obviously right and one that is off by one in some corner you will find three hours later. There is really only one shape:

Maintain lo and hi such that the predicate is false at lo and true at hi, and shrink the gap until they are adjacent.

Everything else — which boundary you want, whether the endpoints are inclusive, what you return — follows from writing down that sentence for the predicate at hand. Problem 80's integer square root is the pattern in its purest form: find $\lfloor\sqrt{S}\rfloor$ for an $S$ far too large for a hardware double, by bisecting on mid * mid <= scaled_number.

low = 0
high = scaled_number
while high - low > 1:
    mid = (low + high) // 2
    if mid * mid <= scaled_number:
        low = mid
    else:
        high = mid
return str(low)[:digits]

Three things are worth copying from those six lines. The invariant is low² ≤ S < high², and it holds at entry and is preserved by both branches. The loop condition is high - low > 1, not low < high — the interval shrinks by at least one every iteration, so it cannot hang, and the answer is low by the invariant rather than by a post-loop adjustment. And the test uses only multiplication, never a division or a square root, so it is exact for arbitrarily large integers. Python's arbitrary-precision int makes that free; the C solution at the same index carries its own big-integer type for exactly this reason.

Two jobs: searching an array, searching the answer

Searching an array is the familiar one, and in Python it is a library call — bisect for lists, np.searchsorted for arrays; in C, bsearch or a hand-written upper_bound. Sorted prime arrays are the recurring subject. Problem 187 counts semiprimes as $\pi\!\left(\frac{N-1}{p}\right) - \pi(p-1)$ over small primes $p$, and gets one of those two terms for nothing: in a dense ascending prime array the index of a prime already is the count of primes below it, so only the upper end needs a search. Problem 501 does the same for a three-shape divisor count, problem 231 locates where $b^i \le n$ stops holding, problem 772 finds the $\sqrt{k}$ boundary that splits primes contributing one factor from those contributing several. The array is sorted because it was generated sorted; the search costs nothing to add.

Put a prefix-sum array next to the sorted one and the same search answers a richer question: it returns the sum of every element $\le x$, not just how many there are. Problem 516 needs exactly that. It sums the $n \le L$ whose totient is 5-smooth, and those $n$ factor as $h \cdot m$, with $h$ a Hamming number and $m$ a squarefree product of primes $q > 5$ for which $q-1$ is itself a Hamming number. For a fixed $m$, every admissible $h$ contributes, so that $m$'s share of the sum is $m \cdot \sum_{h \le L/m} h$. That is one bisection and one prefix lookup:

total += m * prefix[bisect_right(hamming, limit // m)]

The proportions are what make this the right shape. There are only about 3,400 Hamming numbers below $10^{12}$, so the array fits in L1 cache, but there are millions of products $m$. Each query costs a dozen probes, and nobody ever lists the $n$ themselves. Problem 565's first solution has the same shape, a sum of $g(p)$ over primes up to $x$, read from a prefix array at a bisected index. Problem 678 uses the array as a multiset: for each $b$ it forms the whole row of sums $a^e + b^e$ and looks the row up in one searchsorted call against the sorted table of targets $c^f$, so a value that is a perfect power two ways ($2^6 = 4^3$) counts twice.

The search can also be the coarse half of a two-level lookup. Problem 341 evaluates the Golomb sequence at $10^6$ cubes up to $10^{18}$. A table of $G$ that far is out of the question, but the sequence is constant on long blocks, and inside a block the prefix sum it needs is a quadratic in the index. So the solution stores only the block ends, about $2.6 \times 10^4$ of them. One vectorised searchsorted places every query in its block, and the quadratic formula, followed by a one-step integer correction, finds the exact position inside the block. Search the coarse table, solve inside the block. The table can be small because each entry covers a stretch where the quantity has a closed form.

A sorted list also makes a good cache. Problem 829 builds, for each tree shape, the sorted list of every number of that shape up to some bound, which is expensive to generate. It keeps the list together with the largest bound computed so far. A later request for a smaller bound is a bisect_right on that list's prefix, and only a larger bound regenerates. Because the list is sorted, one cache answers "everything up to $x$" for every $x$ below its high-water mark.

Searching the answer is the interesting one, and the array is imaginary. All you need is a monotone predicate over the integers (or the reals) and a cheap way to evaluate it:

problem	the axis you bisect	the monotone quantity
80	the integer $x$	$x^2$ against the scaled radicand
156	$n$ over $[0, 10^{12}]$	$f(n,d)$, the digit-$d$ tally, non-decreasing in $n$
235	the real ratio $r$	the closed-form partial sum $s(5000)$, strictly falling
305	the integer $N$ of the concatenation	$C(N)$, occurrences of a digit string starting inside $1..N$, non-decreasing
564	$x = a_{\max}/2R \in (0, 1]$	the half-angle residual of a cyclic polygon, increasing
587	the count $n$ of circles	the area ratio $\rho(n)$, strictly falling
686	the index $J$	$\mathrm{count}(J)$, the hits so far, non-decreasing
800	the prime index $j$	$q\ln p + p\ln q$, increasing in its larger argument
844	the parameter $k$	a node polynomial $f(k)$, increasing for $k \ge T$ (checked, not assumed)
986	the move count $M$	feasibility of a forced move plan, true then false

The pattern is always the same two ingredients, and it is worth naming them because finding them is the actual work: an $O(\text{cheap})$ evaluator for a quantity you would otherwise have to enumerate, and a proof that the quantity is monotone along the axis you intend to halve. Problem 686 is the extreme case — it wants the $n$-th power of two whose decimal expansion starts with a given digit string, and by equidistribution such hits are sparse enough that the index sought runs into the billions. A Euclidean-style floor-sum evaluates $\mathrm{count}(J)$ in $O(\log m)$ without touching a single power of two, and because $\mathrm{count}$ is non-decreasing, binary search finds the smallest $J$ reaching $n$ in another logarithmic factor. The whole solve is $O(\log^2 n)$ — a few thousand big-integer operations, regardless of how large the answer is.

Problem 686's search lands on the answer directly, because each index holds at most one hit. When the axis is coarser than the thing you are counting, the search finds a bucket, and the counting function finds the rank inside it. Problem 305 wants the position of the $n$-th occurrence of $\text{str}(n)$ in the Champernowne digit stream $123456789101112\ldots$, which for a 7-digit pattern lies around digit $10^{12}$. It does not bisect over digit positions. It bisects over the integers being concatenated, with $C(N)$ the number of occurrences that start inside one of $1..N$. The smallest $N$ with $C(N) \ge n$ is the integer the wanted occurrence starts in, and $n - C(N-1)$ says which of the few occurrences starting there it is. That residue is resolved by scanning a few dozen characters, not by a second search:

rank = n - count(hi - 1)        # which occurrence inside integer hi

Choosing the integer as the axis is what makes $C$ cheap. Counted per integer, every occurrence either sits wholly inside one integer or crosses a boundary, and both classes reduce to closed forms in the digits of $N$ (the crossing class through a congruence on the next integer). Counted per digit position, there is no structure to exploit. The general move is invert a counting function: when you want the $n$-th item, binary search the smallest prefix whose count reaches $n$, then subtract to get the rank. And choose the prefix's unit so that the count has a formula. There is one more lesson in 305. The few occurrences that swallow a short integer whole do not fit either formula, so the solution enumerates those $O(L^2)$ candidates once, before the search starts, and folds them into every $C(N)$ as a fixed list. Fix the irregular cases up front, so that the predicate the loop calls stays a pure formula.

Note that the evaluator is usually the hard part and the search is the easy part. Once problem 587 has a closed form for $\rho(n)$, "find the least $n$ with $\rho(n) \le p$" is thirty lines of bisection over long long. Getting the closed form took an integral.

You rarely know `hi` — bracket first

Textbook binary search is handed both ends. Real ones usually know only that the answer is somewhere above here, which is why several of these solutions bracket before they bisect: start from a known-safe lo, double hi until the predicate flips, then halve. Exponential search is the standard name; problems 587, 686, 235 and 305 all do it.

Doubling costs another $O(\log)$ — asymptotically free — and it buys something better than speed: the bound becomes proved rather than guessed. A hand-picked ceiling is a silent correctness risk, because a binary search over an interval that does not contain the answer returns an endpoint with total confidence. Problem 686 illustrates the discipline: it estimates the ceiling from the density of hits ($\approx 1/L$ per index), then doubles until $\mathrm{count}(hi) \ge n$ before trusting it. The estimate makes the doubling short; the doubling makes the estimate safe. Problem 305 skips the estimate entirely and doubles from hi = 1. Each $C(N)$ costs only $O(L^2)$ arithmetic, so the forty-odd extra evaluations are cheaper than deriving a density bound would be. Problem 829 starts the doubling from a proved lower bound instead: the smallest number of a given tree shape is at least the product of its two subtrees' minima, so it doubles up from there until the generator finds a candidate. Problem 986 solves a chain of instances, so it warm-starts each one. Its bracket is the previous answer scaled by the known growth rate, $(k/(k-1))^3$, plus a 10% margin. A neighbouring instance is usually the best estimate you have.

Sometimes the best bracket comes from changing variables. Problem 564 needs the circumradius $R$ of a cyclic polygon, and $R$ has no natural upper end. In the normalised variable $x = a_{\max}/2R$ the interval is exactly $(0, 1]$, and both of the problem's cases (centre inside or outside the polygon) give a residual that is increasing in $x$. One substitution supplies the bracket and the monotonicity together.

Problem 156 is the same instinct applied in reverse, and worth studying as the general form. It wants every fixed point of $f(n,d) = n$, not the single crossing of a threshold, so there is no boundary to bisect toward. Instead it keeps a stack of intervals $[lo, hi]$ and uses monotonicity to kill each one wholesale: if $f(lo,d) > hi$ then $f(n,d) > n$ everywhere inside, and if $f(hi,d) < lo$ then $f(n,d) < n$ everywhere inside. Anything that survives both tests is split at the midpoint and re-examined. That is binary search with the "one root" assumption removed — the halving and the monotone pruning survive, the uniqueness does not.

Many searches at once, and trusting the result

A textbook binary search is sequential: each probe depends on the one before. Two of these problems break that, in different directions.

Many equations, one loop. Problem 564 solves the circumradius equation for every integer partition of $n - 3$, more than a hundred thousand of them for the largest $n$. Bisection with a fixed step count does the same thing to every row: the same number of halvings, the same comparison, then np.where to keep the correct half. So all the rows advance together as arrays, and nothing has to wait for the slowest row to converge:

for _ in range(64):
    mid = (lo + hi) / 2
    up = residual(mid) < 0
    lo, hi = np.where(up, mid, lo), np.where(up, hi, mid)

Newton's method would converge in fewer steps per row, but each row would need a different number of steps. A loop that runs a fixed number of times is what makes vectorisation possible.

One search, many probes per round. Problem 986 wants the largest feasible move count $M$, and each test is a long simulation. The simulation is vectorised across columns, so testing 64 candidates costs about as much as testing one. The search is therefore a binary search with 64 evenly spaced probes per round instead of one midpoint (a $k$-ary search), and each round shrinks the bracket 64-fold. The two kinds of verdict also cost different amounts. An infeasible $M$ shows itself early, and a feasible one only after a much longer run. So each round stops the simulation once no new infeasible verdict has appeared for a while, and treats the columns still running as feasible.

That cut-off is a heuristic, and the search does not rely on it. The rule that makes it safe: certify the answer, don't trust the loop. When the bracket closes, one exact run must find $M$ feasible and $M + 1$ infeasible. By monotonicity, those two facts are the proof that $M$ is the threshold, however the bracket was found. If the check fails, the bracket widens and the search runs again. Once a final two-point check guarantees correctness, the loop that gets there can be as aggressive and approximate as you like. The same applies to any search whose probes are cheap but inexact, such as floating-point evaluators, sampled tests, or early-terminated simulations.

The awkward parts

Which boundary, and the off-by-one. bisect_left and bisect_right (C++'s lower_bound and upper_bound) differ only in where they put an element equal to the key, and picking the wrong one gives an answer that is right on every test case without duplicates. Decide from the invariant, not from memory of the names.

An insertion point is not a match. Binary search over a discrete array answers "where would this go", which is not the same as "what is nearest". When the question is closest to a target you must look at the neighbours of the insertion point, because the target generally falls between two entries. Problem 85 wants the grid whose rectangle count is nearest two million; rectangle count factors as $T(H) \cdot T(W)$ over triangular numbers, so for each width it bisects the sorted triangular numbers and then explicitly considers both sides of the landing spot:

j = bisect.bisect_left(a=numbers, x=target_num_rectangles // num_width)
for height in (j + 1, j + 2):
    if 0 <= height - 1 < len_numbers:
        results[(num := (numbers[height - 1] * num_width))] = (height, width, height * width)

The same care shows up in problem 461's combine step and in the two-pointer sweeps below: test j and j+1, always.

Floating point. Bisecting on a real parameter is safe in a way that most numerical methods are not, because it consumes only the sign of the residual — the one quantity rounding is least likely to corrupt. Problem 235 chooses bisection over Newton's method deliberately for that reason: with values spanning eleven orders of magnitude, Newton's quadratic convergence buys nothing that sixty halvings have not already delivered, while bisection cannot diverge and needs no derivative. Problem 564 makes the same choice for a sharper reason. Its residual contains an arcsine, whose derivative blows up at $x = 1$, and that is where the roots of nearly degenerate polygons lie, so Newton would be least reliable exactly where it is needed. Two habits go with it. Stop on a tolerance several guard digits below the precision the answer is reported to, so the residual interval cannot disturb the final rounding. And where a comparison decides membership rather than a limit, widen it by a small epsilon — problem 461 admits pairs within pi + 1e-6 precisely so that rounding cannot silently discard a pair belonging to the optimal quadruple.

Monotonicity must be real, on the axis you are halving. This is the failure that actually bites. Problem 772 looks like a threshold problem — the least $N$ all of whose $k$-bounded partitions are balanceable — and it is not: the property is not monotone in $N$, since a larger $N$ can be worse. Binary searching that axis would return a confident wrong number. The solve comes from a divisibility characterisation instead, and the binary search survives only in its proper role, finding a boundary in a sorted prime array. Before you bisect, say out loud what is monotone and why.

When the predicate is generated rather than written by hand, have the program check it. Problem 844 reduces a family of trees to 75 integer polynomials in $k$, and for each one binary searches for the last $k$ at which $f(k) \le N$. That search, and the pruning that produced the list, are sound only if every $f$ is increasing for $k \ge T$. The solution does not assume this. It Taylor-shifts the derivative to $k = T + u$ and asserts that every coefficient is positive, which proves the monotonicity it is about to rely on in a few lines of exact integer arithmetic. A monotonicity assumption that fails silently gives a confident wrong answer. A failed assertion just stops the run.

When binary search is the wrong tool

When the queries are sorted too, use two pointers. $n$ binary searches cost $O(n \log n)$; if the targets themselves move monotonically, a single merge-style sweep does the same work in $O(n)$ with no branch misprediction and perfect locality. Problem 461's C solution walks i up from the smallest pair-sum while j walks down, because target = pi - pairs[i].sum decreases as i increases, so j never moves back — one sequential pass instead of millions of searches. Problem 252's C merge and problem 184's rotating-arc count are the same trade. Note what the Python versions of those solutions do instead: they call searchsorted, in chunks, because in vectorised code you cannot break out of a loop — a binary search is the vectorised form of "where does this monotone condition stop". Both are right; the language decides. The precondition matters, though. Problem 516's products come out of a depth-first enumeration in no particular order, and sorting millions of queries just to sweep a few thousand keys would cost more than the searches it saves. See two-pointer technique.

When the key space is structured, index it directly. $O(\log n)$ in an inner loop is still a factor you can delete. Problem 565's first solution answers "sum of $g(p)$ over primes $p \le x$" by binary searching a prefix-sum array over every prime up to $n$. Its second solution notices that the only arguments ever queried are the $O(\sqrt{n})$ distinct values of $\lfloor n/k \rfloor$, stores them in a two-array sqrt-decomposition, and answers each lookup in $O(1)$ — which, together with not materialising the primes, is what lifts the solve from $10^9$ to $10^{11}$. The general move: binary search is what you write when the keys are merely sorted; when they are also predictable, compute the index.

When a hash set would do — unless you are writing C. This is the one place where binary search appears not as an optimisation but as a substitute for a missing container. Problem 49 tests membership among $n$-digit primes and problem 122 tracks a shrinking set of unresolved targets; both use a Python set for $O(1)$ membership, and both use a sorted array plus bsearch in C, because the standard library has no hash set. The asymptotics are worse and it does not matter — at a few hundred elements the contiguous array wins on cache behaviour, deletion is a memmove, and the minimum is remaining[0] in $O(1)$ for free, which the C version of problem 122 uses as its pruning bound. Sorted-array-as-set is a perfectly good data structure when $n$ is small and writes are rare.

How to reason about it

Reach for binary search whenever a quantity is monotone along some axis and you can evaluate it far more cheaply than you can enumerate it. Then, in order:

Name the axis and the predicate. Write the predicate so it is false below the answer and true at and above it. If you cannot write that sentence, you do not have a binary search.
Prove the monotonicity on that axis — not on the quantity the problem talks about. This is where wrong answers come from, and it costs one paragraph of thought. If the predicate is generated, assert it in code. If no axis is obviously monotone, try changing variables.
Make the evaluator cheap. A closed form, a floor-sum recursion, a prefix-sum lookup. The search contributes $\log$; the evaluator sets the constant. If you want the $n$-th item, the evaluator is a count, and the axis is whatever unit makes that count a formula.
Bracket by doubling rather than guessing a ceiling, so the interval provably contains the answer.
State the invariant in the loop, halt on hi - lo > 1, and return the endpoint the invariant names. If that endpoint is a bucket, get the rank inside it by subtraction, $n - C(hi - 1)$.
Check the neighbours if the question was "nearest" rather than "equal".
Certify the endpoint if the probes were approximate: the predicate false at the answer and true one step past it settles it, whatever the loop did to get there.
Batch the probes when the evaluator vectorises: lockstep fixed-step bisection for many equations, $k$-ary probing for one expensive equation.
Then ask whether you need it at all — sorted queries want two pointers, structured keys want direct indexing.

Problems28 / 28

● 0049 — Prime Permutations
● 0080 — Square Root Digital Expansion
● 0085 — Counting Rectangles
● 0122 — Efficient Exponentiation
● 0156 — Counting Digits
● 0184 — Triangles Containing the Origin
● 0187 — Semiprimes
● 0231 — Prime Factorisation of Binomial Coefficients
● 0235 — An Arithmetic Geometric Sequence
● 0241 — Perfection Quotients
● 0252 — Convex Holes
● 0305 — Reflexive Position
● 0341 — Golomb's Self-describing Sequence
● 0461 — Almost Pi
● 0501 — Eight Divisors
● 0516 — $5$-smooth Totients
● 0564 — Maximal Polygons
● 0565 — Divisibility of Sum of Divisors
● 0587 — Concave Triangle
● 0678 — Fermat-like Equations
● 0686 — Powers of Two
● 0772 — Balanceable $k$-bounded Partitions
● 0800 — Hybrid Integers
● 0829 — Integral Fusion
● 0833 — Square Triangle Products
● 0844 — $k$-Markov Numbers
● 0986 — Another Infinite Game
● 1003 — Lonely Singles