Big O Practice: Binary Search Classic

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

Variables

• n - length of the sorted input array

Explanation

Each iteration halves the search range, so the loop runs at most ⌈log₂ n⌉ times - **O(log n)** time. Constant variables only, **O(1)** space. The array must already be sorted.

More Big O practice problems · Today's daily problem