Mastery Points
0
Lower and Upper Bound in dsa
Context & Logic
Lower Bound finds the first index where the element is NOT less than the target. Upper Bound finds the first index where the element is strictly greater than the target.
Example
function lowerBound(arr, target) {
let low = 0, high = arr.length - 1, ans = arr.length;
while (low <= high) {
let mid = Math.floor((low + high) / 2);
if (arr[mid] >= target) { ans = mid; high = mid - 1; }
else low = mid + 1;
}
return ans;
}Step-by-Step Logic
1
Initialize low at 0 and high at n-1.
2
Update the answer and move high to search for an earlier occurrence.
Complexity Metrics
Time Efficiency
O(log n)
Memory Footprint
O(1)