Step 2 — Lower Bound

Plain search tells you whether a value exists, but real indexes need to know where a value would go. lower_bound answers that: it returns the index of the first element that is greater than or equal to target. If every element is smaller, it returns len(arr), the position just past the end.

Implement lower_bound(arr, target):

Use a half-open window lo = 0, hi = len(arr) and loop while lo < hi.
If arr[mid] < target the boundary is to the right, so set lo = mid + 1.
Otherwise arr[mid] is a valid candidate, so set hi = mid (do not discard it).
When the loop ends lo == hi is the answer.

This variant does not stop early on a match. That is deliberate: it always converges on the leftmost valid position, even with duplicates.

Hints

def search(arr, target): lo, hi = 0, len(arr) - 1 while lo <= hi: mid = (lo + hi) // 2 if arr[mid] == target: return mid elif arr[mid] < target: lo = mid + 1 else: hi = mid - 1 return -1 def lower_bound(arr, target): """Return the index of the first element >= target, or len(arr).""" # TODO: half-open search over [0, len(arr)]. Move lo past elements < target. pass

Step 2 — Lower Bound

Implement lower_bound(arr, target):

Use a half-open window lo = 0, hi = len(arr) and loop while lo < hi.

If arr[mid] < target the boundary is to the right, so set lo = mid + 1.

Otherwise arr[mid] is a valid candidate, so set hi = mid (do not discard it).

When the loop ends lo == hi is the answer.

This variant does not stop early on a match. That is deliberate: it always converges on the leftmost valid position, even with duplicates.

Hints