Binary Search

Binary search is an algorithm for locating a target in a sorted array by repeatedly comparing it with the middle element and discarding the half that cannot contain it. The process ends when the target is found or no candidates remain. It is an application of divide and conquer, although only one of the resulting subproblems is pursued at each step. With constant-time element access and comparisons, its worst-case running time is logarithmic in the number of elements. (xlinux.nist.gov)

Ordering and search procedure

For an array sorted in ascending order, a comparison with the middle element has three possible outcomes. If the target is smaller, only the lower portion remains relevant; if larger, only the upper portion remains relevant; if equal, an exact-match search can return immediately. Unlike linear search, binary search does not inspect every preceding element before reaching a candidate. Its ability to exclude entire regions depends on the array being sorted according to the comparison used during the search. (xlinux.nist.gov)

For example, consider [3, 8, 12, 17, 24, 31, 46] and target 24. The initial middle element is 17, so the search continues among 24, 31, 46. Comparing with 31 then excludes the larger values, leaving 24. This illustrates how index boundaries shrink while the underlying array remains unchanged. (algs4.cs.princeton.edu)

Binary search operates on ordered, indexable data rather than requiring a particular numeric representation. Records can be searched through a comparison key, provided their stored order agrees with that key. Descending sequences require reversing the relevant comparison directions. (go.dev)

Boundary-search implementation

A useful variant returns the first position whose value is not less than the target, rather than returning immediately on equality. This position, called the lower bound, is also an insertion point that preserves ascending order. It may equal the array length when every element is smaller than the target. (courses.cis.cornell.edu)

The following pseudocode uses zero-based indices and a half-open interval [lo, hi), which includes lo but excludes hi:

lower_bound(A, x):
    lo = 0
    hi = length(A)

    while lo < hi:
        mid = lo + floor((hi - lo) / 2)
        if A[mid] < x:
            lo = mid + 1
        else:
            hi = mid

    return lo

Here floor rounds down to an integer. If the returned position is p, exact membership is established by checking p < length(A) and A[p] == x. The empty array is handled without accessing any element. (courses.cis.cornell.edu)

Correctness can be expressed through a loop invariant: every element before lo is smaller than x, every element at or beyond hi is at least x, and 0 ≤ lo ≤ hi ≤ n. Each update preserves these statements. The nonnegative interval width strictly decreases, proving termination; when the boundaries coincide, the invariant identifies the required insertion position. Such reasoning is a standard application of formal verification and mathematical proof to program behavior. (courses.cis.cornell.edu)

Complexity and representation

For a nonempty array of length $n$, the conventional exact-match version requires at most $\lfloor\log_2 n\rfloor+1$ iterations. Repeated halving gives logarithmic time complexity, conventionally written $O(\log n)$ using Big O notation. Each iteration requires only a constant amount of work when access and comparison costs are constant. (cs.princeton.edu)

An iterative implementation stores only a fixed number of indices, giving $O(1)$ auxiliary space complexity. An implementation using recursion ordinarily consumes $O(\log n)$ stack space if each call remains on the stack. These bounds concern the search itself, not storage for the input or preliminary sorting. (algs4.cs.princeton.edu)

The choice of data structure matters. An array provides efficient random access, whereas locating middle elements in a linked list requires traversal. Binary search on an ordered linked list can retain $O(\log n)$ comparisons while requiring $O(n)$ traversal work overall. Thus a logarithmic comparison count does not necessarily imply logarithmic execution time. (xlinux.nist.gov)

Duplicate values and insertion points

An exact-match implementation may return any matching occurrence when duplicates exist. Lower-bound search instead identifies the first occurrence. Its counterpart, upper-bound search, finds the first element strictly greater than the target. Together, these boundaries delimit all matching elements; subtracting their indices gives the number of occurrences. Python’s bisect_left and bisect_right expose these two insertion-point conventions. (algs4.cs.princeton.edu)

Finding an insertion point does not make insertion logarithmic. In an array-backed sequence, inserting an element may require shifting a linear number of existing entries. Python’s insort operations therefore take $O(n)$ time despite their logarithmic search step. (docs.python.org)

Generalization and implementation pitfalls

The method extends to a Boolean-valued function that is false on an initial range and true thereafter. Binary search finds the first true position without materializing an array. This is a boundary-search form of monotonicity; Go’s sort.Search explicitly accepts such a predicate and returns the range length if no true position exists. (go.dev)

Boundary conventions must remain consistent: a half-open interval uses different termination and update rules from a fully inclusive interval. Incorrect updates can omit candidates or prevent progress. Another hazard is integer overflow when computing (lo + hi) / 2. For nonnegative, representable bounds, lo + (hi - lo) / 2 avoids overflowing the intermediate sum. (cs.cornell.edu)