Lower Bound (Binary Search)
Problem link: https://www.geeksforgeeks.org/problems/implement-lower-bound/1
Problem Statement
Given a sorted array a and a value x, return the first index i such that a[i] >= x.
If no such index exists, return n (the array length).
Input
a: sorted integer arrayx: integer target
Output
- First index
iwitha[i] >= x, elsen
Example
a = [1, 3, 3, 5, 8], x = 4
output = 3
Explanation
a[3] = 5 is the first value >= 4.
Brute Force
Intuition
Just find the first position where the condition becomes true.
Approach
Scan from left to right; return the first index with a[i] >= x. If none, return n.
Code (Java)
public class LowerBoundLinear {
// Returns the first index i such that a[i] >= x, or n if it doesn't exist.
public static int lowerBound(int[] a, int x) {
for (int i = 0; i < a.length; i++) {
if (a[i] >= x) return i;
}
return a.length;
}
}
Time: O(N)Space: O(1)
Complexity Analysis
- Time
O(N): in the worst case, you may scan allnelements. - Space
O(1): only a few variables are used.
Optimal Solution
Intuition
Think of “first true” in a monotonic boolean array.
Because the array is sorted, the predicate a[i] >= x becomes:
false false false ... true true true
The lower bound is the first index where it becomes true.
Approach
Maintain a search space [lo, hi) such that the answer is always inside it.
- Invariant: all indices
< loare definitely false (a[i] < x) - Invariant: all indices
>= hiare definitely true (or “past the array”) - Shrink until
lo == hi→ that index is the firsttrue
Code (Java)
public class LowerBoundBinarySearch {
// Returns the first index i such that a[i] >= x, or n if it doesn't exist.
public static int lowerBound(int[] a, int x) {
int lo = 0, hi = a.length; // [lo, hi)
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] >= x) {
hi = mid; // mid might be the answer
} else {
lo = mid + 1; // answer is strictly right of mid
}
}
return lo;
}
}
Time: O(log N)Space: O(1)
Complexity Analysis
- Time
O(log N): binary search halves the range each step. - Space
O(1): iterative binary search uses constant extra space.
Quick Revision (Brute Force)
- Scan left to right; first a[i] >= x is the answer.
- If none found, return n.
- Time O(N), Space O(1).
Quick Revision (Optimal)
- Model as first-true over predicate a[i] >= x in sorted array.
- Use [lo, hi) and shrink until lo == hi.
- Time O(log N), Space O(1).