Are there any existing algorithms/strategies to test if an integer value is within the bounds of any of a list of intervals, where each interval is denoted by a [min, max] pair?
The naive approach is very straightforward, but has O(intervals) test performance:
list intervals (min, max)
func testVal(val){
foreach (interval(min, max) in intervals)
if (val > max) || (val < min) return false
return true
}
In the problem I'm facing the list is not updated frequently, but it is tested against with very high frequency.
Thus, it's acceptable for updating the list to be expensive, but tests need to be sublinear, ideally constant time.
One option is to insert every value in the intervals into a hashtable, but this is memory-intensive and not practical when the intervals get large. Memory usage needs to be proportional to the number of intervals, not the sum of the sizes of the intervals (probably ok to have a log(n) memory usage term thrown in if it greatly aids performance).
I've started poking around with various tree-based options to make this better, but it feels like a general enough problem that I suspect there is preexisting work I should be referencing. Are there any existing solutions to get sublinear tests (ideally constant time) on a list of intervals by preprocessing them into some other datastructure(s)?