Intermediate · Module 9 · Lesson 2
Lower & upper bound
Find the first or last position satisfying a predicate.
Lesson 48 of 123
1d streakLower & Upper Bound: Finding First and Last Occurrences
Standard binary search terminates as soon as target is found. Lower bound finds the first index where elements are >= target; upper bound finds the first index where elements are > target. These bounds partition sorted arrays into exact duplicate ranges in O(log n) time.
// First index i where nums[i] >= target
public int lowerBound(int[] nums, int target) {
int low = 0, high = nums.length;
while (low < high) {
int mid = low + (high - low) / 2;
if (nums[mid] >= target) {
high = mid; // Candidate found; search left half
} else {
low = mid + 1;
}
}
return low;
}Active Recall Checkpoint
Why does high initialize to nums.length instead of nums.length - 1 in lower bound?
Show answer & explanation
If all elements in the array are strictly less than target, the insertion point is at index nums.length. Using high = nums.length ensures the full range [0, n] can be returned.
Use it when
Use lower/upper bound to locate frequency count of duplicates in sorted arrays (count = upperBound - lowerBound) and predecessor/successor lookups.
Reconsider when
Reconsider when elements are unordered; linear scanning is required unless the array is queried repeatedly.
Cost Model
Complexity & Trade-offs
Hands-On Practice
Implement: Lower Bound (Binary Search)
Write and test your solution in the browser against automated verification test cases.
Lower Bound (Binary Search)
Given a sorted array of integers nums and an integer target, return the index of the first element that is greater than or equal to target. If no such element exists, return nums.length.
When to use it
- Exact lookup, first/last occurrence, rotated order, and answer-space optimization.
- Any monotonic yes/no feasibility boundary.
- Implicit ordered spaces where values need not be materialized.
Common mistakes
- Mixing inclusive and half-open interval updates.
- Using binary search without proving monotonicity.
- Returning the last middle value instead of the stored boundary.
Practice prompts
- Reproduce the worked Lower & upper bound example without looking at the trace.
- Change one input condition and explain whether the Lower & upper bound invariant still holds.
- Implement the approach, derive its cost, and compare it with a straightforward baseline.
Mastery check