Fix the lower bound search in a hot lookup
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
targetappears more than once, that means the index of its first copy.
Examples
search_sorted_index(sorted_values: list[int], target: int) -> intExample 1
Input
search_sorted_index([1, 3, 5, 7], 5)Output
2Example 2
Input
search_sorted_index([1, 3, 5, 7], 4)Output
2Example 3
Input
search_sorted_index([], 9)Output
0