Find a value in a sorted list
A lookup runs against a sorted index, so scanning from the front would be wasteful when halving the range each time works.
- The values arrive sorted ascending, with no repeats.
- Return the position of the value, counting from zero, or -1 if it is not there.
find_sorted(values: list<int>, target: int) → int
Where you start
def find_sorted(values: list[int], target: int) -> int:
Worked examples
| Call | Result |
|---|---|
find_sorted([1, 3, 5, 7], 5) | 2 |
find_sorted([1, 3, 5, 7], 1) | 0 |
find_sorted([1, 3, 5, 7], 7) | 3 |
find_sorted([1, 3, 5, 7], 4) | -1 |
Hint
Two bounds that close in on each other. Watch that the loop condition includes the case where they meet.
Reference solution in Python
def find_sorted(values: list[int], target: int) -> int:
lo, hi = 0, len(values) - 1
while lo <= hi:
mid = (lo + hi) // 2
if values[mid] == target:
return mid
if values[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1