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.

The invariant, not the value

Binary search does not mean hunting for an exact value; it finds the boundary where a monotonic condition flips. Maintain an interval known to contain the answer, inspect its midpoint, then discard the half that cannot contain the boundary.

Stating the invariant in words before writing the loop is what prevents off-by-one errors. Say exactly what is known to the left of lo and what is known at or to the right of hi.

Define what is known left of lo
Define what is known at or right of hi
Every update must preserve both statements

Half-open intervals and the midpoint

A half-open interval [lo, hi) removes several off-by-one cases: the interval is empty exactly when lo equals hi, and its size is simply hi minus lo. Choose a convention, state it, and make every update preserve it.

Compute the midpoint as lo + (hi - lo) / 2 rather than (lo + hi) / 2. In fixed-width integer arithmetic the second form can overflow for large indices, a bug that sat undetected in widely used binary searches for years.

[lo, hi) is empty exactly when lo equals hi
mid = lo + (hi - lo) / 2 avoids overflow
The interval must shrink every iteration or the loop hangs

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.

Code example

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))

int binary_search(vector<int>& values, int target) {
    int lo = 0, hi = values.size() - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (values[mid] == target) return mid;
        if (values[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

static int binarySearch(int[] values, int target) {
    int lo = 0, hi = values.length - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (values[mid] == target) return mid;
        if (values[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

Inputvalues = [2, 5, 8, 12, 16, 21, 29], target = 16

Outputindex 4

Example

Run the example step by step

Output

Lower bound and upper bound

Lower bound finds the first position whose value is at least the target. Upper bound finds the first position strictly greater. Their difference counts occurrences in sorted data, which turns duplicate handling into a matter of choosing the right comparison.

When duplicates exist, returning on the first equality finds an arbitrary occurrence. Continue toward the desired boundary instead.

First equal: lower bound plus an equality check
Last equal: upper bound minus one
Insertion position: lower bound
Count of a value: upper bound minus lower bound

Binary search on the answer

Sometimes the search space holds candidate answers rather than stored values: minimum capacity, maximum feasible distance, or earliest completion time. Write a predicate feasible(x) whose truth changes only once across the ordered domain, then binary search that domain instead of an array.

The proof has two parts: the predicate must be monotonic, and the interval updates must retain the first or last feasible value requested.

Name the candidate domain and its bounds
Prove the predicate is monotonic
Return the boundary the invariant promised