Binary Search

The machine must find a target in a sorted array and return its index, or -1. Binary search halves the search window each step by comparing the target with the midpoint; every comparison discards half of the remaining elements. The entire problem is getting the midpoint and the bounds right.

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

Steps: (1) maintain an inclusive window [lo, hi], (2) compare the middle element, (3) move one bound past the midpoint and repeat until the window closes.

Time is O(log n): each step halves the range. Space is O(1) for the iterative version.

Trickiest edge cases: the loop bound — lo <= hi with lo = mid + 1 / hi = mid - 1 guarantees progress; lo < hi with unbounded mids can loop forever when the target is absent. Integer overflow on (lo + hi) is a classic bug in C-like languages; lo + (hi - lo) // 2 avoids it. Targets at either end of the array exercise the exit condition exactly.