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
C++ 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
int insertPosition(std::vector<int> values, int target) {
}Worked examples
| Call | Result |
|---|---|
insertPosition(std::vector<int>{1, 3, 5, 6}, 5) | 2 |
insertPosition(std::vector<int>{1, 3, 5, 6}, 2) | 1 |
insertPosition(std::vector<int>{1, 3, 5, 6}, 7) | 4 |
insertPosition(std::vector<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 C++
int insertPosition(std::vector<int> values, int target) {
int lo = 0, hi = (int) values.size();
while (lo < hi) {
int mid = (lo + hi) / 2;
if (values[mid] < target) lo = mid + 1;
else hi = mid;
}
return lo;
}