Is it possible in Java to run a binarySearch on a function of the elements, not the elements themselves?
In other words binary search on f(A[i]), not on A[i].
For example consider this array: [1, 3, 4, 5, 9].
The goal is to find the first element whose square is greater than or equal to 20. (In this case the answer is 5).
Can we achieve this in Java with its binarySearch implementation (and not writing our own binary search)?
I saw there is a version binarySearch which takes a comparator, but I am not sure if it's guaranteed that the first element in comparison would be the element from the array, and the second element would be the target?
binarySearch(T[] a, T key, Comparator<? super T> c)
Also please note "square" is just an example, which has a reverse square root. But in general assume there is no reverse function. ie we want to apply the function on the elements for the binary search.
Another note: Assume the array is sorted, and f(i) is increasing.
I found the answer, which is slightly tricky (hacky).
However I think considering the fact that Java's BinarySearch returning the (-(insertion point) - 1) when the element is not the array, it's a fair game.
The idea is to distinguish the target by for example negating it, so in the compare function if the number is negative we know it's the target (and negate it), and if it's positive it's an array element and we should apply the function.
This is based on the assumption that there is no negative number in the array. If there are negative numbers this method doesn't work.
Here is the code for the example in the question:
import java.util.Arrays;
import java.util.Comparator;
import java.util.function.Function;
public class BinarySearchFx {
public static void main(String[] args) {
Integer[] arr = {1, 3, 4, 5, 9};
Function<Integer, Integer> f = x -> x*x;
Comparator<Integer> comparator = (o1, o2) -> {
o1 = o1 > 0? f.apply(o1) : -o1;
o2 = o2 > 0? f.apply(o2) : -o2;
return o1 - o2;
};
int result = Arrays.binarySearch(arr, -20, comparator);
if (result < 0)
result = -result - 1;
System.out.printf("index: %d, element: %d", result, arr[result]); // prints index: 3, element: 5
}
}