Binary search without the off-by-one guesswork

Binary search is easy to explain and easy to get wrong. left <= right or left < right? mid or mid + 1? Return left or right?

Here's my first attempt at LeetCode 981: Time Based Key-Value Store, which needs the value with the latest timestamp <= target:

def find_value(entries: list[tuple[int, str]], target: int) -> str:
    left, right = 0, len(entries) - 1
 
    while left <= right:
        mid = (left + right) // 2
        timestamp, _ = entries[mid]
 
        if target <= timestamp:
            left = mid
        else:
            right = mid - 1
 
    _, value = entries[left]
    return value

Three bugs. Here's the framework that prevents all of them.

1. Turn the array into Y/N

Ask a yes/no question of each element. In a sorted array, the answers form a block of Ys followed by a block of Ns.

timestamps:  1   2   3   4   5   7   9      target = 5
ts <= 5?     Y   Y   Y   Y   Y   N   N
                             ^   ^
                        last Y   first N

Every binary search finds one of two spots: the last Y or the first N.

2. Use one template

left, right = 0, len(arr) - 1
 
while left <= right:
    mid = (left + right) // 2
 
    if is_yes(arr[mid]):
        left = mid + 1     # mid is a Y: boundary is to the right
    else:
        right = mid - 1    # mid is an N: boundary is to the left

Always step past mid. The window shrinks every loop, so it can't hang.

3. Read the answer from the end state

The loop ends with left == right + 1, straddling the boundary:

• right = last Y (-1 if there are no Ys)

• left = first N (len(arr) if there are no Ns) No extra result variable needed.

Checklist

1. Question? Phrase it so Ys come first.

2. Last Y or first N? Return right or left.

3. Not found? Check right >= 0 or left < len(arr).

Examples

TimeMap: latest timestamp <= target. That's the last Y, so use right.

def find_value(entries: list[tuple[int, str]], target: int) -> str:
    left, right = 0, len(entries) - 1
 
    while left <= right:
        mid = (left + right) // 2
        timestamp, _ = entries[mid]
 
        if timestamp <= target:    # Y
            left = mid + 1
        else:                      # N
            right = mid - 1
 
    if right < 0:                  # no timestamp <= target
        return ""
 
    _, value = entries[right]      # last Y
    return value

Search Insert Position: first element >= target. Ask num < target, so that's the first N: use left.

def search_insert(nums: list[int], target: int) -> int:
    left, right = 0, len(nums) - 1
 
    while left <= right:
        mid = (left + right) // 2
 
        if nums[mid] < target:     # Y
            left = mid + 1
        else:                      # N
            right = mid - 1
 
    return left                    # first N

Same loop. Only the question and the return change.

Python's bisect module follows the same idea: bisect_left(nums, x) is the first index with nums[i] >= x, and bisect_right(nums, x) - 1 is the last index with nums[i] <= x.

The original bugs

1. Wrong question. target <= timestamp marks the Ns, then moves right on them.

2. left = mid. Doesn't step past mid, so it hangs when left == right.

3. No not-found check. Reads entries[left] even when nothing qualifies, and crashes on an empty list. Don't memorize where the + 1 goes. Find the Y/N boundary and let the template do the rest.