Search Insert Position

The machine must return the index where a target is, or where it would be inserted to keep the array sorted — the classic "lower bound" search. The insight: don't special-case found vs not-found. Track the leftmost position that could hold the target and let the loop run until the window closes; the final lo is the answer in both cases.

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

Steps: (1) search with a half-open window [lo, hi), (2) drop everything strictly below the target, (3) the window converges to the first position ≥ target.

Time is O(log n). Space is O(1).

Trickiest edge cases: target smaller than everything — lo never advances and the answer is 0. Target larger than everything — lo climbs to len(nums), a valid insert position past the end. With duplicates, the search returns the first occurrence because the window only ever slides right past values strictly less than the target; use this variant and you never need a separate found-check.