Lower Bound
Scenario
You are querying a database for all logs that occurred after a specific timestamp. The log table has millions of rows sorted by time.
How do you find the exact byte offset of the FIRST log that matches or exceeds your timestamp in O(log N) time?
Why it exists
Problem: Standard binary search is non-deterministic on duplicates. If an array has 5,000 identical elements, standard binary search will return whatever index it happens to hit first, which could be in the middle of the block.
Naive approach: Use standard binary search to find any match, then run a linear scan backwards to find the first occurrence. In the worst case (all duplicates), this degrades to O(N) time.
Better idea: Modify the binary search condition. When you find a match, don't stop. Treat it as an upper limit and continue searching the left half to pinpoint the absolute leftmost occurrence in guaranteed O(log N) time.
Mental model
You are looking for the start of a chapter in a book. You open to a page in the middle of the chapter. You know you need to go backwards, so you keep flipping left until you hit the title page.
Lower Bound returns the index of the first element that is GREATER THAN OR EQUAL TO the target. If `arr[mid] >= target`, the current element is valid, but an earlier valid element might exist to the left. We update `high = mid` (or `mid - 1`) to aggressively search leftward without losing our current valid boundary.
Repeated decision: Is `arr[mid] >= target`? If yes, the leftmost answer is at `mid` or to its left (`high = mid`). If no, the leftmost answer is strictly to its right (`low = mid + 1`).
Explanation
The Lower Bound algorithm fundamentally alters the termination logic of binary search. Instead of halting on a match, it squeezes the search window `[low, high]` inward until the two pointers converge on the precise leftmost boundary.
Crucially, if the target is entirely absent from the array, Lower Bound returns the exact insertion point where the target *should* go to maintain sorted order.
Another powerful engineering detail: Lower Bound does not require the entire array to be fully sorted. It only requires the array to be *partitioned* with respect to a boolean predicate (e.g., `element < target`). This allows you to use Lower Bound on custom object arrays divided by boolean states (e.g., all active users preceding inactive users).
In systems programming, Lower Bound is used for memory allocators to find the smallest free memory block that can satisfy a requested size, minimizing fragmentation.
Key points
- Leftmost Occurrence: Finds the very first instance of a duplicate value in O(log N) time.
- Insertion Point: If the target is absent, it returns the index where it should be inserted to keep the array sorted.
- Predicate Partitioning: Only requires the array to be partitioned by a boolean condition, not strictly sorted.
Pattern: Leftmost Boundary / Insertion Point
Recognition cues:
- The problem asks for the 'first occurrence' of an element.
- The problem asks to find the smallest element that is >= the target.
- The data contains heavy duplicates.
Failure signals
- You used standard binary search and are failing test cases with duplicate values.
- You used binary search and then a `while` loop to scan left, getting Time Limit Exceeded (O(N) fallback).
Engineering examples
Database Range Queries
Finding the start position for a query like `SELECT * WHERE timestamp >= X`.
Lower bound instantly jumps to the first valid record on disk, establishing the start for a sequential read.
Memory Allocators
Given a sorted list of free memory blocks, find the smallest block that fits an N-byte allocation.
Lower bound finds the first block >= N instantly, ensuring fast allocation with minimal fragmentation.
When not to use
- You need the exact last occurrence: Lower bound only finds the first occurrence. To find the last occurrence, you need the Upper Bound algorithm.
Common mistakes
- Incorrect pointer updates: If `arr[mid] >= target`, writing `high = mid - 1` without saving `mid` as a potential answer will cause you to jump entirely over the true leftmost boundary.
Glossary
- leftmost boundary
- The very first occurrence of a value in a sorted list.
- boolean predicate
- A condition that evaluates to either true or false.
- memory allocators
- Internal computer systems that hand out chunks of memory to programs that need it.
Recall questions
- What does Lower Bound return if the target is entirely missing from the array?
- Why doesn't Lower Bound require a fully sorted array?
- Why is using standard binary search + a linear scan backwards a bad idea for finding duplicates?
Questions & answers
Implement the lower bound algorithm.
Set `ans = len`. While `low <= high`: if `arr[mid] >= target`, update `ans = mid` and `high = mid - 1` (search left). Else, `low = mid + 1` (search right).
Approach: Lower Bound with tracking variable.
Find the insertion position of a target in a sorted array. If it exists, return its first index.
This is the exact definition of Lower Bound. Run standard Lower Bound and return the converged index.
Approach: Direct Lower Bound application.
Continue learning
Previous: Binary Search
Next: Upper Bound
Next: Binary Search on the Answer
Related: Binary Search
Related: Upper Bound