Here is the implementation of lower bound:
function lowerBound(arr, target):
low = 0
high = arr.length
while low < high:
mid = low + (high - low) / 2
if arr[mid] < target:
low = mid + 1
else:
high = mid
return low
Key differences from exact-match:
high = arr.length (not arr.length - 1) because the answer can be past the end.
while low < high (not <=) because we narrow to a single point.
When arr[mid] >= target, set high = mid (not mid - 1) because mid might be the answer.
Result: low is the first index where arr[low] >= target. If all elements are smaller, low == arr.length.