Search, and the power of a good invariant

01 · Foundation

Why binary search works

Linear search checks elements one at a time: look at index 0, then 1, then 2, and so on until you either find the target or run out of array. That's O(n) — in the worst case you touch every element once.

Binary search does something fundamentally different. At each step it picks a single point, asks one yes/no question about it, and uses the answer to discard half of everything that's left — without ever inspecting most of the discarded half. What makes that safe is a property called monotonicity: as you move across the search space, some predicate about each position is false for a while and then becomes true (or the values are simply ordered, which is the special case "sorted" gives you). Once you know the predicate flips at most once across the whole range, checking the midpoint tells you unambiguously which side the answer is on — you never have to check the other side at all.

That's the real requirement underneath "the array must be sorted." Sortedness is just the most common way a monotonic predicate shows up: "is array[i] ≥ target?" is false for small i and true for large i, with a clean flip point. Whenever you can state a similar false-then-true (or true-then-false) predicate over some ordered space, binary search applies — sorted array or not.

02 · Method

A repeatable framework

Binary search is short to code and surprisingly easy to get subtly wrong. Working through these five decisions, in order, avoids almost every bug people run into.

1. 1 Confirm a monotonic predicate actually existsBefore reaching for binary search, check that your search space really is false-then-true (or ordered) across the range you care about. Forcing it onto unsorted or non-monotonic data doesn't just run slowly — it gives wrong answers.
2. 2 Define lo/hi preciselyDecide up front whether hi is inclusive (the last valid index) or exclusive (one past the last valid index), and stay consistent for the rest of the function. Mixing conventions mid-way is the single biggest source of off-by-one bugs.
3. 3 Compute mid and evaluate the predicateCompute a midpoint between lo and hi, and ask your yes/no question about it — usually "is array[mid] equal to, less than, or greater than the target?"
4. 4 Decide which half to keepBased on the predicate's result, update lo or hi to discard the half that can't contain the answer. This is where off-by-one bugs actually live — make sure the half you discard includes mid itself when it's been ruled out, and the half you keep never accidentally re-includes it.
5. 5 Define the stopping conditionMatch the loop test (lo <= hi vs lo < hi) to the inclusive/exclusive convention you picked in step 2, and decide explicitly what the function returns when the target simply isn't there.

03 · Worked example

Binary search, one comparison at a time

Array [2, 5, 8, 12, 16, 23, 38, 45, 56, 72] (10 elements, indices 0–9), inclusive bounds, target 23. Each row is one loop iteration: compute mid, read array[mid], decide.

Three iterations, each one a single comparison, and the range went from 10 candidates to exactly 1. Notice lo and hi only ever move inward — that's the invariant from the callout above being maintained by hand, one step at a time.

04 · Complexity

How to reason about time & space

Every iteration removes half of whatever's left, so the number of iterations to get down to a single element is the number of times you can halve n before hitting 1 — that's log₂ n by definition. Time complexity: O(log n).

• Iterative implementation — a couple of variables (lo, hi, mid) updated in a loop, no extra memory proportional to input size: O(1) space.
• Recursive implementation — logically identical, but each recursive call adds a frame to the call stack until the base case hits: O(log n) space just for the stack.
• Linear search, for contrast — O(n) time, because there's no way to skip elements without the monotonic structure binary search relies on. For a million-element array, that's the difference between roughly 20 comparisons and up to a million.

05 · Generalization

Beyond array lookup — binary search on the answer

Here's the part that matters more than the array version: binary search doesn't need a literal sorted array to work. All it needs is a range of possible answers and a feasibility check — some function that takes a candidate answer and returns "yes, this works" or "no, this doesn't" — where the check is monotonic across the range (once it flips from no to yes, it stays yes for every larger, or every smaller, candidate).

When that holds, you can binary search directly over the space of possible answers, even though nothing is stored or sorted anywhere. Pick a candidate in the middle of your answer range, run the feasibility check, and use the yes/no result to discard half of the remaining candidates — exactly the same loop as the array version, just with "is arr[mid] big enough?" replaced by "does this candidate answer actually work?"

A few classic phrasings that are quietly asking you to do this:

• "What's the minimum capacity/time/rate such that the whole task can be done within a limit?" — e.g. "find the minimum ship capacity that lets all packages be delivered within D days." Binary search over capacity; the check is "can this capacity finish in time?" (a smaller capacity that fails means every smaller one fails too — monotonic).
• "Minimize the maximum ..." — e.g. "split the array among k workers to minimize the largest single worker's load." Binary search over the candidate maximum load; the check is "can we split the array into ≤ k groups each within this load?"
• "Find the smallest/largest value such that some condition holds." — any time the condition is true for every value past some threshold and false before it (or vice versa), that threshold is exactly the kind of monotonic flip point binary search is built to find, whether or not "value" ever refers to an array index.

The mental shift is: stop asking "is my data sorted?" and start asking "if I fixed a candidate answer, could I cheaply check whether it works — and would that check's answer flip at most once as I sweep the candidate up or down?" If yes, you have a binary search, regardless of what the input looks like.

06 · Before you start coding

Common mistakes

• Mixing bound conventions — e.g. initializing hi = n (exclusive) but looping on lo <= hi (an inclusive-style test). The two don't agree on what "one past the end" means, and the result is an off-by-one error or an infinite loop.
• Applying binary search to data that isn't actually monotonic for the property you're checking — sorting by one field and then binary searching on a different, unrelated field, for instance.
• An update that doesn't shrink the range — lo = mid without also making sure mid moved forward (should usually be lo = mid + 1, or use a mid formula that rounds toward the side you're updating). Get this wrong and the loop never terminates.
• Computing mid = (lo + hi) / 2 and assuming it's always safe — in JavaScript's number type this isn't a practical concern, but in fixed-width integer languages lo + hi can overflow. The standard safe idiom is mid = lo + (hi - lo) / 2, which never sums two large values directly.
• Not handling "not found" explicitly — decide up front what the function returns (an index, -1, "insertion point," etc.) when the loop ends without a match, instead of leaving it as an accident of however the loop happens to exit.

07 · Try it

See it animate

One visualizer currently covers this category directly — but everything above applies well past this one use case.