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
Go 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
func findSorted(values []int, target int) int {
}Worked examples
| Call | Result |
|---|---|
findSorted([]int{1, 3, 5, 7}, 5) | 2 |
findSorted([]int{1, 3, 5, 7}, 1) | 0 |
findSorted([]int{1, 3, 5, 7}, 7) | 3 |
findSorted([]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 Go
func findSorted(values []int, target int) int {
lo, hi := 0, len(values)-1
for lo <= hi {
mid := (lo + hi) / 2
if values[mid] == target {
return mid
}
if values[mid] < target {
lo = mid + 1
} else {
hi = mid - 1
}
}
return -1
}