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.
insertPosition(values: list<int>, target: int) → int
Go needs a compiler and Drill does not host one yet, so this page is the reference rather than an exercise: the problem, worked examples, and the solution in full. To type it out, the same problem runs in Python.
Where you start
func insertPosition(values []int, target int) int {
}Worked examples
| Call | Result |
|---|---|
insertPosition([]int{1, 3, 5, 6}, 5) | 2 |
insertPosition([]int{1, 3, 5, 6}, 2) | 1 |
insertPosition([]int{1, 3, 5, 6}, 7) | 4 |
insertPosition([]int{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 Go
func insertPosition(values []int, target int) int {
lo, hi := 0, len(values)
for lo < hi {
mid := (lo + hi) / 2
if values[mid] < target {
lo = mid + 1
} else {
hi = mid
}
}
return lo
}