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
public int FindSorted(List<int> values, int target) {
}Worked examples
| Call | Result |
|---|---|
FindSorted(new List<int> { 1, 3, 5, 7 }, 5) | 2 |
FindSorted(new List<int> { 1, 3, 5, 7 }, 1) | 0 |
FindSorted(new List<int> { 1, 3, 5, 7 }, 7) | 3 |
FindSorted(new List<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#
public int FindSorted(List<int> values, int target) {
int lo = 0, hi = values.Count - 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;
}