Binary Search in Python: Keep the Answer in Range

Imagine looking up a name in an alphabetized directory. You can open it in the middle and decide which half still contains the name. Binary search applies the same idea to an array. Its shortcut has one condition: the order must let us discard half without losing the answer.

Why the array must be sorted

Let numbers = [2, 5, 8, 12, 17, 23, 31] and search for 17. The middle value is 12. Every value to its left is at most 12, so 17 must be on the right. With values in arbitrary order, that conclusion would fail.

Each comparison leaves at most half of the previous range. Search takes O(log n) time for n elements, while this iterative version uses O(1) extra space. Sorting the input is not included in that time bound.

Which boundaries to keep

Use two inclusive boundaries: left is the first possible index, and right is the last. The range is nonempty while left <= right. Its middle index is (left + right) // 2.

If the middle value is below the target, discard it and everything to its left with left = middle + 1. If it is above the target, use right = middle - 1. Equality means we found the answer. Moving past the middle matters: without it, the loop could stall on a one-element range.

A simple Python implementation

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

Indices start at zero. With an empty array, right starts at -1, so the loop never runs and the function returns -1. If a value occurs more than once, this version returns one matching index; it does not promise the first or last.

This search handles exact matches in an ordinary sorted array. Finding a duplicate boundary, searching a rotated array, or finding the smallest feasible number changes the rule for selecting a half. The restricted “Binary Search in Python” material walks through those three cases. Its product page lists the contents, price and access terms; sales are currently closed.