# Binary Search Done Right — DSA Interview Patterns

Source: https://www.skillbyai.com/en/dsa-interview-patterns/b-lower

> One template, no off-by-one bugs.

## 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.

![Three ideas: lower bound, search on the answer, monotonic stacks.](assets/figures/dsa-interview-patterns/section-4-map.svg) — Figure 4.1 — Lower bound, answer search and stacks.

## 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.

```python
# 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.

**Quiz:** What does lower bound return for a target larger than all elements?

- [x] The length of the array
- [ ] -1
- [ ] 0
- [ ] The last index

*Answer:* The length of the array. It is the insertion point.