What is binary search?

How it works

Because the array is sorted, checking the middle tells you which half the target must be in. You throw away the other half every time, which is why it is so fast compared to scanning every element.

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

Key points

• The array must be sorted first.
• Time complexity is O(log n) because the range halves each step.
• Space complexity is O(1) for the loop version.