Build polynomial function from a set of intervals denoting y >= 0

Question

I have a set of ordered, non-overlapping intervals that do not share boundaries, e.g.:

long[][] intervals = new long[][]{
    new long[]{ 2, 3 },
    new long[]{ 5, 10 },
    new long[]{ 25, 1200 },
    ...
}

Currently I use a binary search algorithm to find out if value x is contained by one of the ranges. This is a lot CPU work and involves looping over ranges.

My idea is now to form a polynomial function where y >= 0 exactly when one interval contains the value x and y < 0 if not. This function can be calculated up front and be reused: I pass any x and can use the resulting y to see if it is fine or not.

Advantages I expect over the binary search:

• If I have a limited set of ranges I can prepare the function to be reused over multiple x where when using the binary function I would need to run it again for every `x´ again.
• Only one if (for deciding if smaller than 0 or not)

How can I build such polynomial function given a set of intervals?

Answer 1

Are you looking for something like this?

public static void main(String[] args) {
    long[][] intervals = new long[][]{
            new long[]{2, 3},
            new long[]{5, 10},
            new long[]{25, 1200}
    };
    long numberToFind = 26;
    long[] interval = findInterval(intervals, numberToFind);
    if (interval.length > 0) {
        System.out.println(numberToFind + " is in range: " + interval[0] + " to " + interval[interval.length - 1]);
    }else {
        System.out.println(numberToFind + " is not in range");
    }

}

private static long[] findInterval(long[][] intervals, long numberToFind) {
    for (long[] interval : intervals) {
        if (numberToFind >= interval[0] && numberToFind <= interval[interval.length - 1]) {
            return interval;
        }
    }
    return new long[0];
}