Binary Search Done Right

Half-open ranges and lower bound

Most binary search bugs come from inconsistent boundaries. A reliable template searches the half-open range [lo, hi) for the first index where a condition becomes true (lower bound): if nums[mid] < target move lo = mid + 1, otherwise hi = mid. It returns the insertion point when the target is absent and the first occurrence when duplicates exist. Python's bisect module implements the same thing.

Halve the space, remember the pending

Binary search halves the search space; stacks remember unfinished items until they are resolved.

Lower bound compared with bisect_left, run

I ran this with Python 3.12.3 (standard library only). The custom search agrees with bisect_left: the first 3 is at index 1, 4 would be inserted at 4, and out-of-range targets give 0 or the length.

# Binary search: first index with value >= target (lower bound)
import bisect

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

nums = [1, 3, 3, 3, 7, 9]
for t in (3, 4, 0, 10):
    print(t, "->", lower_bound(nums, t), "bisect_left:", bisect.bisect_left(nums, t))

Output:

3 -> 1 bisect_left: 1
4 -> 4 bisect_left: 4
0 -> 0 bisect_left: 0
10 -> 6 bisect_left: 6

Think "first true"

Frame every binary search as finding the first position where a monotonic condition flips from false to true.

Quick check: What does lower bound return for a target larger than all elements?

• The length of the array
• -1
• 0
• The last index