Binary Search Explained

Binary search finds a target in a sorted sequence by repeatedly discarding half of the remaining candidates. Instead of checking every item, compare the target with the middle item and keep only the half that could contain it.

Before starting, you should be comfortable with Python lists, Python loops, and Python functions. New to programming? Start with Intro to Python.

How binary search works

For an ascending list, keep two inclusive indices: low and high.

1. Start with low = 0 and high = len(array) - 1.
2. Find the middle index with mid = low + (high - low) // 2.
3. If array[mid] equals the target, return mid.
4. If the middle value is too small, set low = mid + 1.
5. If the middle value is too large, set high = mid - 1.
6. Repeat while low <= high. If the interval becomes empty, return -1.

The list must already be sorted using the same ordering as the comparisons. On unsorted input, discarding a half could discard the target.

A binary search example, step by step

Find 23 in [4, 8, 12, 16, 23, 28, 32]. Indices start at zero.

If the target were 24, the third comparison would move low to 5. Now low > high, so the result would be -1.

Binary search in Python

This iterative implementation returns an index, not the value. It does not change or copy the input list.

def binary_search(array, value):
    low = 0
    high = len(array) - 1
 
    while low <= high:
        mid = low + (high - low) // 2
        if array[mid] == value:
            return mid
        if array[mid] < value:
            low = mid + 1
        else:
            high = mid - 1
 
    return -1
 
 
numbers = [4, 8, 12, 16, 23, 28, 32]
print(binary_search(numbers, 23))  # 4
print(binary_search(numbers, 24))  # -1
print(binary_search([], 23))      # -1

The invariant is: if the target exists and has not been found, it is between low and high, inclusive. Each comparison preserves that rule. The + 1 and - 1 also guarantee that the interval shrinks, so the loop terminates.

Time and space complexity

After one unsuccessful comparison, at most half the candidates remain. After two, at most a quarter remain. Repeated halving takes O(log n) time in the worst case and O(1) time in the best case when the first middle item matches. An empty list needs no comparisons.

For a nonempty list of n items, at most floor(log2(n)) + 1 middle-item checks are needed. Even a million items need at most 20 checks. The iterative version uses O(1) auxiliary space because it stores only a few indices.

These bounds assume constant-time indexing, as Python lists provide. A linked list cannot jump directly to its middle. Sorting an unsorted list first usually costs O(n log n), so for a single lookup, a linear scan may be cheaper. Binary search is especially useful for repeated lookups in data that is already sorted.

Edge cases and common mistakes

Try these checks after defining the function:

assert binary_search([], 5) == -1
assert binary_search([5], 5) == 0
assert binary_search([5], 2) == -1
assert binary_search([1, 3, 5, 7], 1) == 0
assert binary_search([1, 3, 5, 7], 7) == 3
assert binary_search([1, 3, 5, 7], 4) == -1
assert binary_search([-9, -2, 0, 6], -2) == 1

• Use <=, not <, with these inclusive bounds, or you may skip the final candidate.
• Move beyond mid. Assigning low = mid can cause an infinite loop.
• Use integer division // to get a valid index.
• Avoid slicing the list at each step: copies add work and lose the original index offset.
• Check for -1 before indexing the result: in Python, array[-1] means the last item.

What if the list contains duplicates?

The implementation returns a matching index, not necessarily the first. For [2, 2, 2], it returns 1. To find the first occurrence, record the matching index and continue searching to its left instead of returning immediately.

Python's standard library already provides insertion-point search. bisect_left gives the first position where the target could be inserted, so you still need to check for equality:

from bisect import bisect_left
 
numbers = [1, 2, 2, 4]
target = 2
index = bisect_left(numbers, target)
found = index if index < len(numbers) and numbers[index] == target else -1
print(found)  # 1

Practice and next steps

Implement the algorithm in the Binary Search puzzle, then adapt it in First Occurrence. The first puzzle uses distinct integers and expects the zero-based index or -1.

Next, read Binary Search Tree Explained. A binary search tree stores ordered values in linked nodes; binary search is an algorithm over a search interval. They share an ordering idea, but are different concepts.