Home / Python / Example programs / Lists

Python program: Binary search

Find a value in a sorted list by halving the search range each step.

The code

def binary_search(items, target):
    low, high = 0, len(items) - 1
    steps = 0
    while low <= high:
        steps += 1
        mid = (low + high) // 2
        if items[mid] == target:
            return mid, steps
        if items[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1, steps

data = list(range(0, 1_000_000, 3))
print(binary_search(data, 299_997))
print(binary_search(data, 5))

Output

(99999, 17)
(-1, 18)

How it works

Each step throws away half of what is left, so even 333,334 items need at most about 19 steps. The list must be sorted. The bisect module provides this.

Python features used

Learn the ideas behind it in the free lesson Loops.