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
Java 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 findSorted(List<Integer> values, int target) {
}Worked examples
| Call | Result |
|---|---|
findSorted(Main.<Integer>ls(1, 3, 5, 7), 5) | 2 |
findSorted(Main.<Integer>ls(1, 3, 5, 7), 1) | 0 |
findSorted(Main.<Integer>ls(1, 3, 5, 7), 7) | 3 |
findSorted(Main.<Integer>ls(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 Java
int findSorted(List<Integer> values, int target) {
int lo = 0, hi = values.size() - 1;
while (lo <= hi) {
int mid = (lo + hi) / 2;
int v = values.get(mid);
if (v == target) return mid;
if (v < target) lo = mid + 1;
else hi = mid - 1;
}
return -1;
}