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

Question

I have a really large list of consecutive natural numbers from 0 to 10**9. We will call every index in this array a key. There's a monotonically increasing function f(key) that generates a value for each key. I want to find the key corresponding to a given target value of f(key). This can be solved using Collections.binarySearch(list, key, comparator), where the comparator uses f(key) for comparing values to the target key.

However, creating and storing an array of 10**9 elements takes a lot of time and memory. I want something like Collections.binarySearch() that operates on a range of natural numbers instead. How do I do this?

Please assume that it is not viable to calculate the inverse of f(key). Also, I'm looking for a O(log n) solution where n is the size of the range of keys.

Here's a motivating example: https://www.geeksforgeeks.org/maximize-number-of-days-for-which-p-chocolates-can-be-distributed-consecutively-to-n-people/ . I want to avoid implementing the binary search myself.

Answer 1

No one said you needed to create all the elements ahead of time to make a collection ;)

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

E.g.

// 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 and higherKey are actually special cases of this function, and floorKey should be easily written by looking "next to" the locations indicated by these.

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