Finding edges, not just hits
Plain binary search asks "is the target present". Often you want more: the first slot where the target could go, or the slot just after its last copy. These are lower bound and upper bound.
Definitions
- Lower bound returns the first index whose value is not less than the target. If the target exists, this is its first occurrence; otherwise it is the insertion point.
- Upper bound returns the first index whose value is strictly greater than the target. This sits just past the last occurrence.
Why they are handy
- The count of a value equals upper bound minus lower bound.
- Inserting while keeping the array sorted means inserting at the lower bound.
- Range queries on sorted data use both edges to mark the window.
Implementation note
Both are binary searches that never stop early on a match. Instead they keep narrowing toward the edge, adjusting only one bound on each comparison. The subtle difference is whether equality moves the search left or right, which decides first versus last occurrence.
Key idea
Lower bound and upper bound turn binary search into an edge finder, giving insertion points and exact duplicate counts from sorted data.