Lower Bound Search
You'll learn how to find the leftmost valid insertion point in a sorted array.
What Is Lower Bound Search?
Lower bound search is a variant of binary search that finds the first position where a value could be inserted while keeping the array sorted. Unlike standard binary search, which only tells you if an element exists, lower bound answers: "Where does this value belong?"
Think of it like finding where to insert a new card into an already-sorted hand of playing cards—you want the leftmost spot where it fits.
How It Differs from Standard Binary Search
Standard binary search stops when it finds a match (or reports "not found"). Lower bound search continues until it identifies the first position where array[position] >= target. This means:
- If the target exists, you get its first occurrence
- If the target doesn't exist, you get where it would be inserted
The Core Idea
Use binary search, but instead of returning on equality, keep narrowing toward the left. When you find a candidate position, check if you can move further left while still maintaining the "greater than or equal" property.
The algorithm adjusts the search space:
- If
array[mid] < target, search right (moveleft = mid + 1) - If
array[mid] >= target, this could be the answer, but keep searching left (moveright = mid)
Eventually, left converges to the lower bound position.
Why It Matters
Lower bound is essential for:
- Finding the first occurrence of duplicates
- Implementing range queries (find all elements in
[a, b]) - Insertion into sorted collections
- Many library functions (C++'s
lower_bound, Python'sbisect_left)
Key Takeaway: Lower bound search finds the leftmost insertion position for a target value in O(log n) time, returning where the value is or should be.