Implement binary search correctly — and explain the off-by-one traps.

How to think about it

Nobody fails this question on the idea — “halve the search space, O(log n)” is the easy part. What the interviewer is really watching is whether your boundary conditions are clean. Do you mix lo <= hi with hi = mid? Do you write lo = mid and loop forever? The whole signal is in the three lines that update lo and hi, so the move is to pick one interval convention and stay inside it.

Binary search applies any time the space is sorted or monotone and one comparison can throw away half of it. That extends well beyond arrays — answer ranges (“the smallest feasible value”), time, even function outputs. The cue to listen for is “the space is ordered, and one check cuts it in half.”

The cleanest convention is the closed interval [lo, hi], where both ends are live candidates. You loop while lo <= hi, take mid = lo + (hi - lo) // 2 (the subtraction form dodges integer overflow in Java or C++; Python ints are unbounded, but it is a good habit). If nums[mid] == target you are done; if it is too small the answer lives in [mid+1, hi], so lo = mid + 1; if it is too big, hi = mid - 1. Move at least one step every time — that is what guarantees the loop ends.

A worked example

def binary_search(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:                       # closed interval: both ends valid
        mid = lo + (hi - lo) // 2         # subtraction form avoids overflow
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            lo = mid + 1                  # answer is to the right
        else:
            hi = mid - 1                  # answer is to the left
    return -1                             # never found

# Find the leftmost occurrence (lower bound) — a SEPARATE half-open template
def lower_bound(nums, target):
    lo, hi = 0, len(nums)                 # hi is ONE past the last index
    while lo < hi:                        # strict less-than, not <=
        mid = lo + (hi - lo) // 2
        if nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid                      # keep mid as a candidate
    return lo                             # index of first element >= target

print(binary_search([1, 3, 5, 7, 9], 7))   # exact hit
print(binary_search([1, 3, 5, 7, 9], 6))   # absent
print(lower_bound([1, 2, 2, 2, 3], 2))     # first 2
print(lower_bound([1, 2, 2, 2, 3], 4))     # past the end
print(binary_search([], 1))                # empty array

3
-1
1
5
-1

Read the outputs against the two templates. The exact-match search returns index 3 for 7 and -1 for the missing 6. The lower-bound search points at the first 2 (index 1) when the value exists, and lands at 5 — one past the last index — when nothing is >= 4, which is exactly the “insertion point” semantics you want. The empty-array call returns -1 without ever entering the loop, because lo=0, hi=-1 fails lo <= hi on the first check.