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
public int InsertPosition(List<int> values, int target) {
}Worked examples
| Call | Result |
|---|---|
InsertPosition(new List<int> { 1, 3, 5, 6 }, 5) | 2 |
InsertPosition(new List<int> { 1, 3, 5, 6 }, 2) | 1 |
InsertPosition(new List<int> { 1, 3, 5, 6 }, 7) | 4 |
InsertPosition(new List<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#
public int InsertPosition(List<int> values, int target) {
int lo = 0, hi = values.Count;
while (lo < hi) {
int mid = (lo + hi) / 2;
if (values[mid] < target) lo = mid + 1;
else hi = mid;
}
return lo;
}