Binary search is simple in idea but one of the most bug-prone algorithms in practice. In this topic we look at boundary traps, the first and last occurrence among duplicates and the standard bisect module.
![Lower and upper bound for 2 in [1, 2, 2, 2, 5, 8]](img/lessons/algorithms/binary-search-pitfalls-bounds.svg)
Boundaries: closed and half-open intervals
In the previous topic we used the closed interval [lo, hi] (hi = len(a) - 1, lo <= hi, hi = mid - 1). For duplicates and "insertion points" the half-open template [lo, hi) is handier: hi = len(a), lo < hi, hi = mid. Each template has its own invariant and mixing them gives IndexError, an infinite loop or an off-by-one error. The rule: pick one template and keep all three parts (start, condition, update) together.
First and last occurrence: lower_bound and upper_bound
lower_bound(a, x) is the first position i where a[i] >= x; upper_bound(a, x) is the first where a[i] > x. Both return a position in 0..len(a) (not a cell) and point to an order-preserving place even when x is absent. The first occurrence is lower_bound, the last upper_bound - 1, the count upper_bound - lower_bound. Presence is checked with i < len(a) and a[i] == x.
