Binary search

Applies to: general

Binary search finds a value in a sorted array in O(log n) by repeatedly halving the search range: compare the middle, then discard the half that cannot contain the 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

See also: big-o, sorting, array