Lesson 12 — Binary search: first occurrence (lower bound)

Lower bound: the FIRST position, even with duplicates

Plain binary search (Lesson 4) returns some match. With duplicates like [1, 2, 2, 2, 3] you often need the first one. The lower bound of t is the first index whose value is ≥ t. It also tells you where to insert t to keep the list sorted. The trick: when a[mid] ≥ t, do not stop — remember mid could be the answer and keep searching left (hi = mid).

# a = [1, 2, 2, 2, 3, 5]
# lower_bound(a, 2) -> 1   (first 2)
# lower_bound(a, 4) -> 5   (4 would go before 5)

Why it matters: "first time at least X" questions (first log after 9:00, first price ≥ budget) are everywhere. Python's bisect.bisect_left does exactly this.