Binary Search

Linear search was optimal for unordered data. If the assumption changes, the bound changes too: if the array is sorted, a single comparison eliminates not one element but half of the remaining ones.

This lesson works through that idea. The idea is simple; writing it correctly is not — binary search is known for having carried bugs in published implementations for decades.

The Range Invariant

The algorithm keeps a range where the target can be found, and halves that range on every iteration. The way to avoid boundary errors is to write down the meaning of the range from the very start.

This lesson uses a closed range: both bounds of [low, high] are included in the range.

def binary_search(array: list[int], target: int) -> int:
    """A position of the target in the sorted array; -1 if not found.

    Invariant: if the target is in the array, it is within [low, high].
    Termination: high - low decreases by at least one every iteration.
    """
    low, high = 0, len(array) - 1
    while low <= high:
        mid = low + (high - low) // 2
        if array[mid] == target:
            return mid
        if array[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1


sorted_array = [1, 3, 4, 7, 9, 11, 15, 20]
print(binary_search(sorted_array, 9))      # 4
print(binary_search(sorted_array, 1))      # 0
print(binary_search(sorted_array, 20))     # 7
print(binary_search(sorted_array, 10))     # -1

Three details carry the correctness of the implementation:

The loop condition low <= high. Because the range is closed, a single-element range is also valid; writing < would leave the last element never tested.

Updating the bounds with mid ± 1. The tested element is left outside the range. Writing high = mid may leave the range unshrunk and put the loop into an infinite state — the termination guarantee comes precisely from this step.

Computing the midpoint as low + (high - low) // 2. Writing (low + high) // 2 can overflow for large arrays in languages that use fixed-width integers. The overflow behavior from the How Computers Work course turns into a concrete bug here.

Cost

Every iteration halves the range and does constant work:

$$T(n) = T(n/2) + O(1) \implies T(n) = O(\log n)$$

The number of comparisons in the worst case is $\lfloor \log_2 n \rfloor + 1$.

from collections.abc import Sequence


def counted_binary_search(array: Sequence[int], target: int) -> tuple[int, int]:
    low, high, count = 0, len(array) - 1, 0
    while low <= high:
        mid = low + (high - low) // 2
        count += 1
        if array[mid] == target:
            return mid, count
        if array[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1, count


for n in (1_000, 1_000_000, 1_000_000_000):
    # range is indexable, so a billion-element array is tested without allocating memory
    even_numbers = range(0, 2 * n, 2)
    print(n, counted_binary_search(even_numbers, n + 1)[1])   # an odd number: not in the array

# 1000 10
# 1000000 20
# 1000000000 30

Thirty comparisons are enough for a billion-element array. Linear search does the same work with a billion comparisons — this is the concrete counterpart of the scale-growth table in the Reading Complexity Classes lesson.

The space cost is $O(1)$. The same algorithm can also be written recursively, but in that case it uses $O(\log n)$ stack space.

Lower Bound: Why Nothing Faster Exists

Comparison-based search produces one of three outcomes at every step: less, equal, greater. If the algorithm’s behavior is drawn as a decision tree, every leaf of the tree is a possible answer, and an array of $n$ elements has at least $n$ different answers.

A binary tree of height $h$ can have at most $2^h$ leaves. From $2^h \geq n$ it follows that $h \geq \log_2 n$: comparison-based search is $\Omega(\log n)$.

The same decision-tree idea will be reused for sorting’s lower bound.

First and Last Position

If the array has repeated values, the implementation above returns any match. Many sorting-related operations, however, want the first match.

The lower bound is the position of the first element not less than the target. If there is no match, it gives the position where the target could be inserted without breaking the order.

def lower_bound(array: list[int], target: int) -> int:
    """The smallest i satisfying array[i] >= target (len(array) if none).

    Invariant: the answer is within [low, high]; the range is kept half-open.
    """
    low, high = 0, len(array)
    while low < high:
        mid = low + (high - low) // 2
        if array[mid] < target:
            low = mid + 1
        else:
            high = mid
    return low


repeated = [1, 3, 3, 3, 7, 9, 9]
print(lower_bound(repeated, 3))      # 1   — first 3
print(lower_bound(repeated, 9))      # 5   — first 9
print(lower_bound(repeated, 4))      # 4   — insertion point
print(lower_bound(repeated, 10))     # 7   — end of the array

This variant uses a half-open range: high is not included in the range. This is why the loop condition is low < high and the update is high = mid. Mixing the two variants is the most common source of bugs in binary search — how the range is kept is chosen once, and every line is written accordingly.

The upper bound finds the first element greater than the target; the difference between the two results gives how many times the target occurs in the array.

Beyond the Sorted Array

Binary search’s real condition is not “the array is sorted” but something more general: the existence of a monotone predicate. If a condition is false up to a certain point and always true after it, that point can be found with binary search.

def integer_sqrt(n: int) -> int:
    """The largest k satisfying k*k <= n."""
    low, high, answer = 0, n, 0
    while low <= high:
        mid = low + (high - low) // 2
        if mid * mid <= n:
            answer = mid
            low = mid + 1
        else:
            high = mid - 1
    return answer


print(integer_sqrt(0), integer_sqrt(15), integer_sqrt(16), integer_sqrt(10**18))
# 0 3 4 1000000000

There is no array here; what is being searched for is the last value at which the predicate mid * mid <= n stays true. Because the predicate is monotone, halving is valid.

This generalization is a common design tool: problems of the form “smallest sufficient capacity” or “largest valid threshold” are solved directly with binary search over the range of candidate values.

When Not to Use It

Binary search rests on three assumptions, and it is not preferred once one of them breaks.

If sortedness does not come for free. Sorting the array for a single search is $O(n \log n)$; linear search is $O(n)$. Sorting pays for itself only when there are many queries.

If there is no random access. Reaching the middle element in a linked list is linear, and the logarithmic gain vanishes. The search trees from the Data Structures course fill exactly this gap.

If the data keeps changing. Updating a sorted array on every insertion is $O(n)$; a balanced tree or a hash table is more suitable in this case.

Summary

• Binary search halves the range in sorted data; its correctness is justified by an invariant that keeps the meaning of the range fixed.
• The closed and half-open range variants require different loop conditions and updates; the two must not be mixed.
• Cost is $O(\log n)$, following from $T(n) = T(n/2) + O(1)$; space is $O(1)$.
• The decision-tree argument shows that comparison-based search is $\Omega(\log n)$.
• The lower-bound variant gives the first match or the insertion position.
• The method applies to any problem that searches for the first value at which a monotone predicate becomes true.

Next Step

Binary search’s condition was sortedness; so sorting itself must now be examined. The next lesson covers three basic sorting algorithms — bubble, selection, and insertion — along with their quadratic costs, their stability, and the points where they differ from one another.