Problems › TypeScript › warmup
Find a value in a sorted list
A lookup runs against a sorted index, so scanning from the front would be wasteful when halving the range each time works.
- The values arrive sorted ascending, with no repeats.
- Return the position of the value, counting from zero, or -1 if it is not there.
findSorted(values: list<int>, target: int) → int
Where you start
function findSorted(values: number[], target: number): number {
}Worked examples
| Call | Result |
|---|---|
findSorted([1,3,5,7], 5) | 2 |
findSorted([1,3,5,7], 1) | 0 |
findSorted([1,3,5,7], 7) | 3 |
findSorted([1,3,5,7], 4) | -1 |
Hint
Two bounds that close in on each other. Watch that the loop condition includes the case where they meet.
Reference solution in TypeScript
function findSorted(values: number[], target: number): number {
let lo = 0;
let hi = values.length - 1;
while (lo <= hi) {
const mid = Math.floor((lo + hi) / 2);
if (values[mid] === target) return mid;
if (values[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return -1;
}