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