How do I write binary search without off-by-one errors?

def binary_search(nums, target):
    low, high = 0, len(nums) - 1

    while low <= high:
        mid = low + (high - low) // 2

        if nums[mid] == target:
            return mid
        if nums[mid] < target:
            low = mid + 1
        else:
            high = mid - 1

    return -1

O(log n). Four rules, all interdependent:

1. high = len(nums) - 1 — inclusive upper bound.
2. while low <= high — the range is still non-empty when they are equal.
3. mid + 1 and mid - 1 — always exclude the midpoint you just tested.
4. Return -1 after the loop.

Change one without the others and you get an infinite loop or a missed match.

#Why not (low + high) // 2

In languages with fixed-size integers, low + high can overflow on a huge array. low + (high - low) // 2 is identical arithmetically and cannot overflow. Python has arbitrary-precision integers so it does not matter there — but the habit is correct everywhere else, and interviewers notice.

#Finding the insertion point

def lower_bound(nums, target):
    low, high = 0, len(nums)      # exclusive upper bound
    while low < high:             # strict
        mid = low + (high - low) // 2
        if nums[mid] < target:
            low = mid + 1
        else:
            high = mid            # NOT mid - 1
    return low

Different template, different rules — exclusive bounds, strict <, and high = mid. Returns where the target belongs, which also handles "first element ≥ target".

Python's bisect.bisect_left does this for you.

#Where else it shows up

Binary search is not only for sorted arrays. Any monotonic predicate works — "what is the smallest capacity that finishes in time?", "what is the minimum speed?". If you can answer yes/no for a candidate and the answer flips exactly once as the candidate grows, you can binary search over the answer space.