What goes in the blank?
# lower_bound: first index with a[i] >= x
lo, hi = 0, len(a)
while lo < hi:
mid = (lo + hi) // 2
if a[mid] < x:
lo = mid + 1
else:
hi = ____
Answer: mid
a[mid] >= x, so mid may itself be the answer and must stay in the window [lo, hi). Using mid - 1 would skip it.
Play Problem Solving ▸