从一组表示y>=0的区间构建多项式函数

Question

我有一组有序的、不重叠的间隔，它们不共享边界，例如：

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

目前，我使用二进制搜索算法来确定值x是否包含在其中一个范围内。这需要大量的CPU工作，并且涉及到范围内的循环。

我现在的想法是形成一个多项式函数，其中

我期望二进制搜索的优势：

• 如果我有一组有限的范围，我可以准备函数，以便在多个x上重用，在使用二进制函数时，我需要再次为每个` x `运行它

如何在给定一组区间的情况下构建这样的多项式函数？

Answer 1

你想要这样的东西吗：

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];
}