Where a value slots in
A timeseries store keeps an array sorted and needs to know exactly where a new reading would land on insertion.
- The values arrive sorted ascending; repeats are allowed.
- Return the position where the value fits so the array stays sorted.
- If the value is already present, return the position of its first occurrence.
- The answer can be anywhere from zero to the length of the list.
insert_position(values: list<int>, target: int) → int
Where you start
def insert_position(values: list[int], target: int) -> int:
Worked examples
| Call | Result |
|---|---|
insert_position([1, 3, 5, 6], 5) | 2 |
insert_position([1, 3, 5, 6], 2) | 1 |
insert_position([1, 3, 5, 6], 7) | 4 |
insert_position([1, 3, 5, 6], 0) | 0 |
Hint
A lower-bound binary search: hold a window in two indices and ask which half the value must fall in.
Reference solution in Python
def insert_position(values: list[int], target: int) -> int:
lo, hi = 0, len(values)
while lo < hi:
mid = (lo + hi) // 2
if values[mid] < target:
lo = mid + 1
else:
hi = mid
return lo