Binary Search

Linear scan — check every position

Walk from left to right and stop when you find target. This is correct, but it treats a sorted array like an unsorted one.

def search(nums: list[int], target: int) -> int:
    for index, value in enumerate(nums):
        if value == target:
            return index
    return -1

Time O(n). Space O(1). In the worst case, you inspect every value.

Binary search — halve the candidates

Keep a closed interval [left, right] containing every index that could still hold the answer. Compare its middle value with target:

• If they're equal, you've found the index.
• If the middle value is smaller, discard the left half with left = middle + 1.
• If the middle value is larger, discard the right half with right = middle - 1.

def search(nums: list[int], target: int) -> int:
    left, right = 0, len(nums) - 1
    while left <= right:
        middle = left + (right - left) // 2
        if nums[middle] == target:
            return middle
        if nums[middle] < target:
            left = middle + 1
        else:
            right = middle - 1
    return -1

Each comparison cuts the live interval roughly in half. Moving past middle matters: you've already proved that position isn't the answer, and keeping it would risk an infinite loop.

Time O(log n). Space O(1). The interval shrinks in place; no extra collection is needed.