Lesson 3 · Core algorithms

Binary Search

Binary search finds a boundary in a monotonic truth pattern. Maintain an interval known to contain the answer, inspect its midpoint, then discard the half that provably cannot hold the boundary.

Maintain an Invariant, Not a Guess

Binary search finds a target in a sorted sequence by repeatedly halving the range that could still contain it. Each comparison eliminates half the remaining candidates, so n elements are resolved in O(log n) steps — about 20 comparisons for a million elements, 30 for a billion.

The algorithm is famously easy to describe and famously hard to write correctly. Jon Bentley reported that most professional programmers fail to produce a correct implementation given several hours, and the bug in Java's own binarySearch survived nine years in the standard library. The cause is always the same: writing the loop by intuition rather than from a stated invariant.

So state it first. The invariant is the property true before and after every iteration — typically if the target exists, it lies within [lo, hi). Every line of the loop then has a job: the midpoint splits the range, the comparison decides which half still satisfies the invariant, and the update discards the other half without ever excluding the target.

Three questions answered up front eliminate nearly all bugs. What does the range include — is hi a valid index or one past the end? Does the loop run while lo < hi or lo <= hi — and that follows from the first answer, not from preference. Is the midpoint excluded when narrowing — writing hi = mid versus hi = mid - 1 depends on whether mid has already been ruled out.

Answer those consistently and the implementation is mechanical. Answer them inconsistently and you get an infinite loop, a skipped element, or an out-of-bounds read — the three classic failures, each traceable to a mismatch between the range convention and the update.

Halving the range gives O(log n) — 20 steps for a million elements
Write the invariant before the loop, then derive the conditions
Decide what the range includes, and let that fix the loop test
Most bugs are a mismatch between the convention and the update

Half-Open Ranges and the Midpoint

The half-open convention [lo, hi) — lo included, hi excluded — produces the cleanest code, and it is worth adopting deliberately rather than switching between styles.

Under it, hi starts at n rather than n − 1, the loop runs while lo < hi, and an empty range is exactly lo == hi. The size of the range is simply hi − lo, with no off-by-one correction. Narrowing is lo = mid + 1 when the target must be to the right, since mid has been ruled out, and hi = mid when it must be to the left, since hi is exclusive and mid is thereby already excluded.

The asymmetry between those two updates is not a mistake — it falls directly out of the convention, and noticing that is what makes the code memorable rather than something to recall under pressure.

The midpoint overflow is the subtle one. Writing mid = (lo + hi) / 2 adds two indices that may each be near the maximum integer, and their sum can wrap to a negative value. This was the Java library bug. Write mid = lo + (hi - lo) / 2 instead: the difference is always within range, so nothing overflows. Python's arbitrary-precision integers make it harmless there, but the habit is worth keeping.

Termination must also be argued, not assumed. Each iteration must strictly shrink the range. Since integer division rounds down, mid can equal lo when the range has two elements — so an update of lo = mid rather than lo = mid + 1 leaves the range unchanged and loops forever. This is the standard infinite-loop bug, and it appears specifically in the variants that search for a boundary rather than an exact value.

[lo, hi): hi starts at n, loop while lo < hi, empty is lo == hi
lo = mid + 1 and hi = mid — the asymmetry follows from the convention
Use lo + (hi − lo) / 2 to avoid integer overflow
Every iteration must shrink the range or the loop never ends

Lower Bound and Upper Bound

Plain binary search answers whether a value is present and returns some index of it. With duplicates, that is rarely enough — you usually want the first occurrence, the last, or how many there are. Two boundary searches cover all of it.

Lower bound returns the first position where the target could be inserted while keeping the array sorted: the index of the first element not less than the target. If the target is present, this is its first occurrence; if absent, it is the insertion point.

Upper bound returns the first position where the target could be inserted after all equal elements: the index of the first element strictly greater than the target.

Together they bracket every occurrence. The count of a value is upperBound − lowerBound, and the value is present exactly when that difference is positive — or equivalently when lowerBound points at an element equal to the target.

The implementations differ from plain search in one important way: there is no early exit. Finding an equal element does not end the search, because an earlier equal element may still exist. The loop always runs to lo == hi, and the comparison changes from three-way to two-way — for lower bound, arr[mid] < target moves lo past mid, and everything else moves hi to mid.

That single comparison difference is the entire distinction between the two: upper bound uses arr[mid] <= target. Standard libraries expose both — lower_bound and upper_bound in C++, bisect_left and bisect_right in Python — and reaching for them rather than hand-writing the loop is usually correct.

The three searches and what each returns
Search	Returns	Comparison at mid
Exact	Any index of the target, or not-found	Three-way, exits early
Lower bound	First index ≥ target	`arr[mid] < target`
Upper bound	First index > target	`arr[mid] <= target`
Count of a value	`upper − lower`	—

Lower bound: first element not less than the target
Upper bound: first element strictly greater
Occurrences = upper − lower; present when that is positive
Neither exits early — the loop must run to completion

Key reference

Terms, operations, and practical uses

Interval vocabulary

InvariantThe statement about lo and hi that every iteration must preserve.
Half-open interval[lo, hi) — empty exactly when lo equals hi, with size hi minus lo.
Monotonic predicateA yes/no condition that flips at most once across the ordered domain.

Boundary variants

Lower boundThe first position whose value is greater than or equal to the target.
Upper boundThe first position whose value is strictly greater than the target.
Occurrence countUpper bound minus lower bound, computed without scanning duplicates.

Common failure modes

Overflow(lo + hi) / 2 can overflow fixed-width integers; use lo + (hi - lo) / 2.
Infinite loopAn update that does not shrink the interval, such as lo = mid when mid equals lo.
Unsorted inputBinary search silently returns a wrong answer rather than failing loudly.

Cost

TimeO(log N) — each comparison halves the remaining interval.
SpaceO(1) iteratively; O(log N) call stack if written recursively.
PreconditionSorted, randomly accessible data, or a provably monotonic predicate.

Implementation

Find a target with binary search

def binary_search(values, target):
    lo, hi = 0, len(values) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2   # avoids overflow in fixed-width ints
        if values[mid] == target:
            return mid
        if values[mid] < target:
            lo = mid + 1            # the target must lie to the right
        else:
            hi = mid - 1            # the target must lie to the left
    return -1


print('index', binary_search([2, 5, 8, 12, 16, 21, 29], 16))

#include <iostream>
#include <vector>
using namespace std;
int binary_search(vector<int>& values, int target) {
    int lo = 0, hi = values.size() - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2; // avoids overflow in fixed-width ints
        if (values[mid] == target) return mid;
        if (values[mid] < target) lo = mid + 1; // the target must lie to the right
        else hi = mid - 1; // the target must lie to the left
    }
    return -1;
}
int main() {
    vector<int> values = {2, 5, 8, 12, 16, 21, 29};
    cout << "index " << binary_search(values, 16) << '\n';
}

public class Main {
    static int binarySearch(int[] values, int target) {
        int lo = 0, hi = values.length - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2; // avoids overflow in fixed-width ints
            if (values[mid] == target) return mid;
            if (values[mid] < target) lo = mid + 1; // the target must lie to the right
            else hi = mid - 1; // the target must lie to the left
        }
        return -1;
    }
    public static void main(String[] args) {
        int[] values = {2, 5, 8, 12, 16, 21, 29};
        System.out.println("index " + binarySearch(values, 16));
    }
}

Watch it run

Step through it

Running on values = [2, 5, 8, 12, 16, 21, 29], target = 16

Output

Read all 6 Steps

Start with the whole array The interval is the entire array: lo = 0, hi = 6. The array must be sorted for the halving argument to hold.
Inspect the midpoint mid = 0 + (6 - 0) / 2 = 3, so values[3] = 12. Because 12 is less than 16, no position at or left of index 3 can hold the target.
Discard the left half Move lo to mid + 1 = 4. Indices 0 through 3 are eliminated in a single comparison. The interval is now [4, 6].
Inspect the new midpoint mid = 4 + (6 - 4) / 2 = 5, so values[5] = 21. Because 21 is greater than 16, nothing at or right of index 5 can hold the target.
Discard the right half Move hi to mid - 1 = 4. Only index 4 remains, so the interval has narrowed to a single candidate.
Target found mid = 4 and values[4] = 16 equals the target, so the search returns index 4. Seven elements were resolved in three comparisons.

Searching an Answer Space

The most valuable generalisation drops the array entirely. Binary search does not require sorted data — it requires a monotone predicate: a yes/no question over an ordered range whose answer switches from false to true exactly once.

When that holds, the search finds the switching point without any array existing. The candidate range is the set of possible answers, and the predicate is a feasibility check, usually implemented as a function that costs O(n) to evaluate.

The classic example: given n items and k workers, what is the minimum possible maximum load? Ask instead, can the work be split so no worker exceeds capacity C? — a greedy check answerable in O(n). That answer is monotone: if capacity C works, so does anything larger. So binary search over C for the smallest feasible value.

The same shape covers a wide family — the minimum days to complete a shipping schedule, the smallest divisor keeping a sum under a threshold, the maximum minimum distance when placing objects. The tell is a problem asking to minimise a maximum or maximise a minimum, which is almost always this pattern.

The recipe is three steps. Identify the range of possible answers and its bounds — usually a trivial lower and a generous upper. Write the feasibility check and confirm it is monotone; if it is not, the technique does not apply. Binary search for the boundary, and be careful to return the last feasible value rather than the first infeasible one.

The complexity is O(n log R), where R is the size of the answer range — the log factor comes from the search and the n from each feasibility check. Since R is a range of values rather than of input size, that log is typically small even when the range is enormous: searching a billion candidate answers costs 30 checks.

One caution: on floating-point ranges the loop cannot terminate on integer equality. Iterate a fixed number of times — 100 iterations halves the interval far below any useful precision — rather than comparing for equality, which may never hold.

Needs a monotone predicate, not a sorted array
'Minimise the maximum' or 'maximise the minimum' signals this pattern
Binary search the answer range; check feasibility in O(n)
O(n log R); on floating-point ranges, loop a fixed number of times