Fix the lower bound search in a hot lookup

Review the AI's codeEasy12 min

Your task

A hot lookup path searches a sorted list with a hand-written binary search. The first version computed the midpoint as (lo + hi) / 2, which overflows on huge arrays, and returned -1 when the target was missing. The new version returns the lower bound instead: the position where the target is, or where it would go.

An assistant wrote search_sorted_index(sorted_values, target). It is in the editor. It has a bug. Find it and fix it.

Input and output:

  • sorted_values: integers sorted in increasing order. Values can repeat.
  • target: the value to look for.
  • Return an index from 0 to the length of the list.

Rules the tests check:

  • Return the first index whose value is greater than or equal to target.
  • If every value is smaller than target, return the length of the list. An empty list returns 0.
  • When target appears more than once, that means the index of its first copy.

Examples

search_sorted_index(sorted_values: list[int], target: int) -> int
Example 1
Inputsearch_sorted_index([1, 3, 5, 7], 5)
Output2
Example 2
Inputsearch_sorted_index([1, 3, 5, 7], 4)
Output2
Example 3
Inputsearch_sorted_index([], 9)
Output0