Problem Statement
Give a safe binary search template to find the first index where arr[i] >= target and explain off-by-one traps.
Explanation
Use a left closed, right open range so the loop is easy to reason about. While left is less than right, take mid as left plus right minus left floor divided by two. If arr mid is less than target, move left to mid plus one. Else move right to mid. At exit, left is the first index with value greater than or equal to target.
Off-by-one bugs come from mixing closed intervals or updating both pointers the same way. Keeping a consistent invariant that the answer is always within the half open interval helps avoid mistakes.
Code Solution
SolutionRead Only
def lower_bound(a, target):
lo, hi = 0, len(a)
while lo < hi:
mid = (lo + hi) // 2
if a[mid] < target:
lo = mid + 1
else:
hi = mid
return lo