If ranges are disjunct (that is a concrete number can only belong to one range), you can find a range using a binary search. This is O(log(n))
complexity.
If ranges are contiguous, it is also enough to "model" a range using only one number, either with its start or its end. This also applies in your case.
We can list the range boundaries in an int
slice in ascendent order, and we can perform a binary search in this sorted slice. We model ranges with their maximum value since the sequence of ranges is without any holes. This will give us the index of the range. We can store the names in a separate slice, and return the name at the index we just found as the result of binary search.
Here's the surprisingly short implementation, a one-line function:
var ranges = []int{-1, 4, 8, 18, 21, 22}
var names = []string{"", "dog", "cat", "bird", "dog", "bird", ""}
func getName(n int) string {
return names[sort.SearchInts(ranges, n)]
}
Testing it:
nums := []int{-1, 3, 6, 10, 20, 22, 100}
for _, n := range nums {
if name := getName(n); name == "" {
fmt.Printf("Invalid number: %4d
", n)
} else {
fmt.Printf("Number : %4d, Name: %s
", n, name)
}
}
Output (try it on the Go Playground):
Invalid number: -1
Number : 3, Name: dog
Number : 6, Name: cat
Number : 10, Name: bird
Number : 20, Name: dog
Number : 22, Name: bird
Invalid number: 100
Note: this solution is also used in a similar question on the Code Review StackExchange site: Classifying by age
Handling non-contiguous ranges
If ranges would not cover every number (meaning there are "holes" between ranges), then you may easily handle that by adding the holes as "virtual" ranges, and give them the empty string ""
name (which we used for invalid ranges). That's all.
For example, let's modify your original problem to this:
0-4: dog,
5-8: cat,
9-15: bird,
19-21: dog,
22-22: bird,
As you can see, there is a "hole" between 9-15: bird
and 19-21:dog
. The range 16-17
is invalid. Here's how you can map this:
var ranges = []int{-1, 4, 8, 15, 18, 21, 22}
var names = []string{"", "dog", "cat", "bird", "", "dog", "bird", ""}
There is an empty ""
name for the range between 15
and 18
. Testing it:
nums := []int{15, 16, 19}
for _, n := range nums {
if name := getName(n); name == "" {
fmt.Printf("Invalid number: %4d
", n)
} else {
fmt.Printf("Number : %4d, Name: %s
", n, name)
}
}
Output (try this variant on the Go Playground):
Number : 15, Name: bird
Invalid number: 16
Number : 19, Name: dog