没有人说您需要提前创建所有元素来创建集合；）

<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...
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.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
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.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())