Skip to content

Binary search in Python

Textbook

Binary search finds an exact-match index in an array sorted in nondecreasing order. This implementation uses elements and an target. The function returns one matching index or −1 if no match exists; it does not promise the first or last index among duplicates.

The variables left and right store inclusive bounds. The invariant is that if the target exists and has not been found, at least one matching index remains in the current range. The middle index is ((left + right) / 2). If its value is below the target, every index through the middle can be excluded, so left becomes middle + 1. A greater value symmetrically makes right become middle − 1.

Sorted order proves each exclusion safe. Every unsuccessful step strictly shrinks the range, ensuring termination. When left > right, the range is empty; the invariant then implies there is no match. An empty array starts in this state.

For an array of length $n\ge2$, worst-case time is $O(\log n)$ under constant-cost comparisons and indexed access. The iterative version stores a fixed number of variables, using $O(1)$ extra space. Checking or establishing the original sorted order is not included.

A nonempty range contains right − left + 1 positions. After an unsuccessful comparison, at most the of half that many remain, because the middle itself is excluded. This connects termination with the step bound. Keeping the source list unchanged matters to the argument: rearranging elements or changing their order during the search can invalidate the safety of previously discarded halves.

In plain language

In an ordered phone book, comparison with the middle name immediately rules out half the pages. The middle entry itself is excluded after comparison, or the search can reopen the final page forever and call it perseverance. Two bookmarks track the remaining interval, so there is no need to remember every inspected entry. The ordering must remain intact throughout the search; pages rearranged between steps terminate the phone book’s contract without notice.

Example

The target is 17 in the sorted illustrative array [2, 5, 8, 12, 17, 23, 31]. Indices start at zero. The steps below follow the same algorithm as the code.

Binary search in Python

Initial range

The left bound is 0 and the right bound is 6. All seven positions remain possible.

Step 1 of 4: Initial range

Read all steps
  1. Initial range

    The left bound is 0 and the right bound is 6. All seven positions remain possible.

    Values
    25812172331
    Bounds
    left = 0currentright = 6current
  2. The middle value is 12

    Index 3 contains 12, below 17. Indices 0–3 are excluded; left = 4.

    Values
    2excluded5excluded8excluded12current172331
    Remaining
    17included23included31included
  3. The middle value is 23

    Within indices 4–6, the middle is index 5. Its value 23 exceeds the target, so right = 4.

    Values
    2excluded5excluded8excluded12excluded1723current31excluded
    Remaining
    17included
  4. A match

    Both bounds meet at index 4. Its value 17 matches the target: the result is 4.

    Values
    2excluded5excluded8excluded12excluded17included23excluded31excluded
    Index
    4included

For the absent target 18, the first exclusions leave the same index 4 containing 17. The next comparison advances left to 5 while right remains 4, and the function returns −1. That value signals absence rather than a usable result index: Python index −1 would select the list’s last element. Using numbers[index] requires a prior check that a match was found.

def binary_search(numbers: list[int], target: int) -> int:
    left = 0
    right = len(numbers) - 1

    while left <= right:
        middle = (left + right) // 2
        value = numbers[middle]

        if value == target:
            return middle
        if value < target:
            left = middle + 1
        else:
            right = middle - 1

    return -1

numbers = [2, 5, 8, 12, 17, 23, 31]
print(binary_search(numbers, 17))  # 4
print(binary_search(numbers, 18))  # -1

The binary_search function accepts a sorted list numbers and a target, returns an index or −1, and does not mutate the list. For an empty input, right is −1 and the loop never runs. Searching for absent 18 eventually empties the range; a one-element input needs at most one middle-element check.

Finding duplicate boundaries, searching a rotated array, and finding the feasible value change the half-selection rule. Those cases are covered in the paid material “Binary Search in Python”. Its product page lists the contents and current access terms.

The original text of this free article is published under CC BY-NC-ND 4.0.

Previous / next

Previous
Big Theta: a tight growth order
Next
Arithmetic mean of observations
  • Natural Numbers: Counting Discrete Objects

    Which values count discrete objects, and why the zero convention must be stated.

    Read article
    Math
  • Integers: Counting on Both Sides of Zero

    Positive and negative integers, zero, and the limits of integer division.

    Read article
    Math
  • Rational Numbers: Ratios of Integers

    Numbers as ratios of integers: equivalent fractions and the nonzero denominator requirement.

    Read article
    Math