Problems › JavaScript › patterns
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
Where you start
function insertPosition(values, target) {
}Worked examples
| Call | Result |
|---|---|
insertPosition([1,3,5,6], 5) | 2 |
insertPosition([1,3,5,6], 2) | 1 |
insertPosition([1,3,5,6], 7) | 4 |
insertPosition([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 JavaScript
function insertPosition(values, target) {
let lo = 0, hi = values.length;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (values[mid] < target) lo = mid + 1;
else hi = mid;
}
return lo;
}