Overview
Lower Bound is a binary-search variant that keeps the leftmost position whose value is greater than or equal to the target.
CoreSource checked
Lower Bound
Finds the first sorted position where a value could be inserted without breaking order.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Searching
- Difficulty
- Beginner
- Family
- Binary Search Variant
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 2
- Formulas
- 1
- Relationships
- 2
- Code example
- Ready
- Visualization
- Ready
Core Concepts
sorted search spaceinsertion boundaryhalf-open intervalmidpoint comparison
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(1)
Average
O(log n)
Worst
O(log n)
Space
O(1)
When to Use
- Use when duplicates matter and you need the first position at or after the target.
- Use when finding first duplicate position is a central requirement.
When Not to Use
- Avoid when the input is not sorted or the comparison is not consistent.
- Avoid when the input does not preserve the ordering or rank assumption the search relies on.
What It Does
- Searches a sorted range
- Tracks the first valid insertion point
- Handles duplicate values predictably
Use Cases
- Finding first duplicate position
- Range queries in sorted arrays
- Ordered insertion
Inputs
- Sorted array or list
- Target value
Outputs
- First insertion index
Key Formulas (1)
Midpoint index
mid = low + ⌊(high − low) / 2⌋
mid = low + floor((high - low) / 2)Chooses the middle of the active half-open interval.
Pseudocode
- 1.Set low to 0 and high to length
- 2.While low is less than high, check the middle
- 3.If middle value is less than target, move low right
- 4.Otherwise move high to middle
- 5.Return low
Canonical Example
- Input
- values = [1, 3, 3, 5], target = 3
- Output
- index = 1
- Explanation
- The first value that is not less than 3 appears at index 1.
Implementation Notes
- Use a half-open interval [low, high) to make end insertion natural.
- Test lower, upper, duplicate, empty, and not-found cases separately.
- Keep a tiny example with known output beside the implementation.
- Search algorithms should define both success and failure semantics.
Common Pitfalls
- Using high = length - 1 often loses the valid insertion position at the end.
- Boundary conditions around equal values and missing values are easy to handle inconsistently.
- Not defining boundary, empty, or degenerate inputs before implementation.
- Off-by-one bounds, duplicates, and missing-target behavior should be specified before implementation.
Interactive Mechanism Walkthrough
Indexed Interval & Boundary ProbeShow the insertion boundary moving left until the first valid position remains.
Target key: 41low=0, mid=4, high=9
4[0]
9[1]
15[2]
22[3]
27[4]
34[5]
41[6]
49[7]
58[8]
63[9]
Step 1 of 5: Set low to 0 and high to length
array-searchNotes
Lower Bound returns the array length when every value is less than the target.
Sources (2)
What each reference supports for this entry.
The Art of Computer Programming, Volume 3
BookSorting and searching reference supporting Lower Bound probe strategy, comparison structure, or implementation invariant.
Introduction to Algorithms (CLRS)
BookAlgorithms textbook support for Lower Bound invariants, search ordering, correctness argument, or asymptotic analysis.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageVariant ofBinary Search
Lower bound adapts binary search to return the first position where a monotone condition holds.
Related Algorithms
Tags
SearchSorted DataDivide and Conquer