如何在函数调用生成比较器值的较大范围内使用 binary_search？

Question

我有一个非常大的连续自然数列表，从 0 到 10**9。我们将把这个数组中的每个索引称为一个键。有一个单调递增的函数 f(key) 为每个键生成一个值。我想找到与 f(key) 的给定目标值对应的键。这可以使用 Collections.binarySearch(list, key, comparator) 来解决，其中比较器使用 f(key) 将值与目标键进行比较。

但是，创建和存储一个包含 10**9 个元素的数组会占用大量时间和内存。我想要像 Collections.binarySearch() 这样的东西来代替对一系列自然数进行操作。我该怎么做？

请假设计算 f(key) 的倒数是不可行的。另外，我正在寻找一个 O(log n) 解决方案，其中 n 是键范围的大小。

这是一个激励人心的例子：https://www.geeksforgeeks.org/maximize-number-of-days-for-which-p-chocolates-can-be-distributed-consecutively-to-n-people/。我想避免自己实现二进制搜索。

Answer 1

没有人说你需要提前创建所有元素来制作一个集合;)

<R> int binarySearchFunc(int range, IntFunction<? extends R> f, R key, Comparator<? super R> ord) {
    class FunctionList extends AbstractList<R> implements RandomAccess {
        @Override public int size() { return range; }
        @Override public R get(int i) {
            if(i < 0 || i >= range) throw new IndexOutOfBoundsException(i + " not in [0, " + size() + ")");
            return f.apply(i);
        }
    }
    return Collections.binarySearch(new FunctionList(), key, ord);
}

例如

// calculate sqrt(2^60) by binary search on a truncated list of perfect squares
binarySearchFunc(Integer.MAX_VALUE, i -> (long)i * i, 1152921504606846976L, Comparator.naturalOrder());

ceilingKey 和 higherKey 实际上是这个函数的特例， floorKey 应该很容易写出来，只要看一下这些指示的“旁边”位置即可。

// use a REAL optional type if you want to handle null properly
// or just use null instead of optionals if you don't
// Java's optional is just the worst of both worlds -.-
// or just use some other sentinel...
<R> int ceilingFunc(int range, IntFunction<? extends R> f, R key, Comparator<? super R> ord) {
    return -1 - binarySearchFunc(
        range, i -> Optional.of(f.apply(i)), Optional.<R>empty(),
        (x, y) -> {
            if(x.isPresent() && y.isPresent()) return ord.compare(x.get(), y.get());
            // the "mystery element" e satisfies both e < key and x < key -> x < e
            else if(x.isPresent()) return ord.compare(x.get(), key) < 0 ? -1 : 1;
            else if(y.isPresent()) return ord.compare(key, y.get()) > 0 ? 1 : -1;
            else return 0;
       });
}
// almost the same
<R> int higherFunc(int range, IntFunction<? extends R> f, R key, Comparator<? super R> ord) {
    return -1 - binarySearchFunc(
        range, i -> Optional.of(f.apply(i)), Optional.<R>empty(),
        (x, y) -> {
            if(x.isPresent() && y.isPresent()) return ord.compare(x.get(), y.get());
            else if(x.isPresent()) return ord.compare(x.get(), key) > 0 ? 1 : -1;
            else if(y.isPresent()) return ord.compare(key, y.get()) < 0 ? -1 : 1;
            else return 0;
       });
}

// least i with sqrt(i) >= 10
ceilingFunc(Integer.MAX_VALUE, i -> (int)Math.sqrt(i), 10, Comparator.naturalOrder())
// least i with sqrt(i) > 10
higherFunc(Integer.MAX_VALUE, i -> (int)Math.sqrt(i), 10, Comparator.naturalOrder())

如何在函数调用生成比较器值的较大范围内使用 binary_search？

How can I use binary_search on a large range where values for the comparator are generated by function calls?

java

algorithm

binary-search