Binary Search

Find an item in a sorted array by repeatedly halving the search range — O(log n).

Easy

def binary_search(a, target):
    lo, hi = 0, len(a) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if a[mid] == target:
            return mid
        if a[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

A million items need at most 20 comparisons. The same idea finds a root of an equation (bisection), the right resistor in a sorted E-series table, or the first bad commit with git bisect.

Spotted a mistake or want to add detail? Suggest an improvement — Content Contributors' edits are reviewed by editors before they go live.

Discussion (0)