Java 使用自定义函数的二进制搜索
Java binarySearch using custom function
是否可以在 Java 到 运行 中对元素的函数而不是元素本身进行 binarySearch？
换句话说，二进制搜索是在 f(A[i]) 上，而不是在 A[i] 上。
例如考虑这个数组：[1, 3, 4, 5, 9].
目标是找到平方大于或等于 20 的第一个元素。（在本例中答案为 5）。
我们能否在 Java 中使用它的 binarySearch 实现（而不是编写我们自己的二进制搜索）来实现这一点？
我看到有一个带有比较器的 binarySearch 版本，但我不确定是否保证比较的第一个元素是数组中的元素，第二个元素是目标？
binarySearch(T[] a, T key, Comparator<? super T> c)
另外请注意 "square" 只是一个例子，它有一个反平方根。但一般假设没有反向功能。也就是说，我们要将函数应用于二进制搜索的元素。
另一个注意事项：假设数组已排序，并且 f(i) 递增。
是的，有可能，检查一下：
package control;
import java.util.Comparator;
class Testing {
int a;
String b;
Testing(int a, String b) {
this.a = a;
this.b = b;
}
}
public class FunctionalBinarySearch {
private static <T> int binarySearch(T[] array, T t, Comparator<? super T> c) {
int l = 0, r = array.length - 1, m;
while (l <= r) {
m = l + (r - l) / 2;
if (c.compare(array[m], t) == 0) return m;
if (c.compare(array[m], t) < 0) l = m + 1;
else if (c.compare(array[m], t) > 0) r = m - 1;
}
return -1;
}
public static void main(String[] args) {
Testing[] test = new Testing[]{
new Testing(1, "a"),
new Testing(2, "b"),
new Testing(3, "c"),
new Testing(4, "d")
};
System.out.println(binarySearch(test, new Testing(3, "xyz"),
//This lambda is applied as a search criteria function
Comparator.comparingInt(testing -> testing.a)));
//Uses the string comparator
System.out.println(binarySearch(test, new Testing(1, "d"),
Comparator.comparing(testing -> testing.b)));
}
}
备注
- 此二进制搜索算法需要对输入数组进行排序。
- 每次调用都需要指定一个比较器。
- 它 returns 对象的索引（如果有）和 -1（如果 none）。
- 比较器描述了一个搜索条件它是一个 lambda，它可以访问两个对象，并比较属性（如果访问修饰符允许的话）或为这些对象声明的函数。
是的，这是可能的。根据文档：
The method returns the index of the search key, if it is contained in the list; otherwise,
(-(insertion point) - 1). The insertion point is defined as the point at which the key would be inserted into the list: the index of the first element greater than the key, or list.size() if all elements in the list are less than the specified key. Note that this guarantees that the return value will be >= 0 if and only if the key is found.
因此，通过调整返回的索引，您可以获得最接近所需值的位置的下一个值（甚至上一个值）。
其工作原理如下：
- 生成 1 到 20 值的
list。然后调用 n
- 创建一个 lambda，
fn 应用于每个 n。
- 创建一个
Comparator<Integer> comp 使用 fn 进行比较
- 使用
list、n 和 comp 调用 binarySort
- 使用返回的索引为
f(n) 找到最近的 n
这里有一个例子，returns最接近f(n)
的值
Random r = new Random(23);
// define f(n)
Function<Integer, Integer> f = x -> x*x + 2 * x + 3;
Comparator<Integer> comp =
(a, b) -> Integer.compare(f.apply(a), f.apply(b));
for (int i = 0; i < 5; i++) {
// generate a list of f(n) values.
List<Integer> list = r.ints(10, 1, 20).distinct()
.sorted().boxed()
.collect(Collectors.toList());
List<Integer> fns = list.stream().map(f::apply).collect(Collectors.toList());
// Choose a random n
int n = r.nextInt(20);
System.out.println("fns = " + fns);
System.out.println("n = " + list);
// now find nearest f(n) in the list.
int fn = f.apply(n);
System.out.println("searching for nearest value to f(" + n
+ ") [" + fn + "]");
int index = Collections.binarySearch(list, n, comp);
// Now determine the index of the value that
// meets the requirements.
if (index >= 0) {
System.out
.println("Exact answer = " + list.get(index));
System.out.println();
} else {
int nearest;
index = -index - 1;
// check end cases
if (index == 0) {
nearest = list.get(index);
} else if (index == list.size()) {
nearest = list.get(index - 1);
} else {
// check middle cases
int lowerValue = list.get(index - 1);
int higherValue = list.get(index);
if (n - lowerValue > higherValue - n) {
nearest = higherValue;
} else {
nearest = lowerValue;
}
}
System.out.println(
"Nearest result to " + n + " is " + nearest);
System.out.println();
}
}
}
打印：
fn = [18, 51, 66, 83, 102, 123, 171, 291, 363]
n = [3, 6, 7, 8, 9, 10, 12, 16, 18]
searching for nearest value to f(14) [227]
Nearest result to 14 is 12
fn = [6, 11, 38, 51, 83, 198, 326]
n = [1, 2, 5, 6, 8, 13, 17]
searching for nearest value to f(17) [326]
Exact answer = 17
fn = [11, 18, 83, 146, 171, 227, 291, 326]
n = [2, 3, 8, 11, 12, 14, 16, 17]
searching for nearest value to f(0) [3]
Nearest result to 0 is 2
fn = [6, 18, 27, 51, 66, 198, 363]
n = [1, 3, 4, 6, 7, 13, 18]
searching for nearest value to f(1) [6]
Exact answer = 1
fn = [11, 18, 66, 102, 146, 198, 258, 291, 326]
n = [2, 3, 7, 9, 11, 13, 15, 16, 17]
searching for nearest value to f(0) [3]
Nearest result to 0 is 2
我找到了答案，这有点棘手 (hacky)。
但是我认为考虑到 Java 的 BinarySearch 在元素不是数组时返回 (-(insertion point) - 1) 这一事实，这是一个公平的游戏。
这个想法是通过例如取反来区分目标，所以在比较函数中，如果数字是负数，我们就知道它是目标（并取反），如果是正数，它就是一个数组元素，我们应该应用功能。
这是基于数组中没有负数的假设。如果有负数，则此方法不起作用。
这里是问题中示例的代码：
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
}
}
是否可以在 Java 到 运行 中对元素的函数而不是元素本身进行 binarySearch？
换句话说，二进制搜索是在 f(A[i]) 上，而不是在 A[i] 上。
例如考虑这个数组：[1, 3, 4, 5, 9].
目标是找到平方大于或等于 20 的第一个元素。（在本例中答案为 5）。
我们能否在 Java 中使用它的 binarySearch 实现（而不是编写我们自己的二进制搜索）来实现这一点？
我看到有一个带有比较器的 binarySearch 版本，但我不确定是否保证比较的第一个元素是数组中的元素，第二个元素是目标？
binarySearch(T[] a, T key, Comparator<? super T> c)
另外请注意 "square" 只是一个例子，它有一个反平方根。但一般假设没有反向功能。也就是说，我们要将函数应用于二进制搜索的元素。
另一个注意事项：假设数组已排序，并且 f(i) 递增。
是的，有可能，检查一下：
package control;
import java.util.Comparator;
class Testing {
int a;
String b;
Testing(int a, String b) {
this.a = a;
this.b = b;
}
}
public class FunctionalBinarySearch {
private static <T> int binarySearch(T[] array, T t, Comparator<? super T> c) {
int l = 0, r = array.length - 1, m;
while (l <= r) {
m = l + (r - l) / 2;
if (c.compare(array[m], t) == 0) return m;
if (c.compare(array[m], t) < 0) l = m + 1;
else if (c.compare(array[m], t) > 0) r = m - 1;
}
return -1;
}
public static void main(String[] args) {
Testing[] test = new Testing[]{
new Testing(1, "a"),
new Testing(2, "b"),
new Testing(3, "c"),
new Testing(4, "d")
};
System.out.println(binarySearch(test, new Testing(3, "xyz"),
//This lambda is applied as a search criteria function
Comparator.comparingInt(testing -> testing.a)));
//Uses the string comparator
System.out.println(binarySearch(test, new Testing(1, "d"),
Comparator.comparing(testing -> testing.b)));
}
}
备注
- 此二进制搜索算法需要对输入数组进行排序。
- 每次调用都需要指定一个比较器。
- 它 returns 对象的索引（如果有）和 -1（如果 none）。
- 比较器描述了一个搜索条件它是一个 lambda，它可以访问两个对象，并比较属性（如果访问修饰符允许的话）或为这些对象声明的函数。
是的，这是可能的。根据文档：
The method returns the index of the search key, if it is contained in the list; otherwise,
(-(insertion point) - 1). The insertion point is defined as the point at which the key would be inserted into the list: the index of the first element greater than the key, orlist.size()if all elements in the list are less than the specified key. Note that this guarantees that the return value will be >= 0 if and only if the key is found.
因此，通过调整返回的索引，您可以获得最接近所需值的位置的下一个值（甚至上一个值）。
其工作原理如下：
- 生成 1 到 20 值的
list。然后调用n - 创建一个 lambda，
fn应用于每个 n。 - 创建一个
Comparator<Integer> comp使用fn进行比较 - 使用
list、n和comp 调用 binarySort
- 使用返回的索引为
f(n) 找到最近的
n
这里有一个例子，returns最接近f(n)
Random r = new Random(23);
// define f(n)
Function<Integer, Integer> f = x -> x*x + 2 * x + 3;
Comparator<Integer> comp =
(a, b) -> Integer.compare(f.apply(a), f.apply(b));
for (int i = 0; i < 5; i++) {
// generate a list of f(n) values.
List<Integer> list = r.ints(10, 1, 20).distinct()
.sorted().boxed()
.collect(Collectors.toList());
List<Integer> fns = list.stream().map(f::apply).collect(Collectors.toList());
// Choose a random n
int n = r.nextInt(20);
System.out.println("fns = " + fns);
System.out.println("n = " + list);
// now find nearest f(n) in the list.
int fn = f.apply(n);
System.out.println("searching for nearest value to f(" + n
+ ") [" + fn + "]");
int index = Collections.binarySearch(list, n, comp);
// Now determine the index of the value that
// meets the requirements.
if (index >= 0) {
System.out
.println("Exact answer = " + list.get(index));
System.out.println();
} else {
int nearest;
index = -index - 1;
// check end cases
if (index == 0) {
nearest = list.get(index);
} else if (index == list.size()) {
nearest = list.get(index - 1);
} else {
// check middle cases
int lowerValue = list.get(index - 1);
int higherValue = list.get(index);
if (n - lowerValue > higherValue - n) {
nearest = higherValue;
} else {
nearest = lowerValue;
}
}
System.out.println(
"Nearest result to " + n + " is " + nearest);
System.out.println();
}
}
}
打印：
fn = [18, 51, 66, 83, 102, 123, 171, 291, 363]
n = [3, 6, 7, 8, 9, 10, 12, 16, 18]
searching for nearest value to f(14) [227]
Nearest result to 14 is 12
fn = [6, 11, 38, 51, 83, 198, 326]
n = [1, 2, 5, 6, 8, 13, 17]
searching for nearest value to f(17) [326]
Exact answer = 17
fn = [11, 18, 83, 146, 171, 227, 291, 326]
n = [2, 3, 8, 11, 12, 14, 16, 17]
searching for nearest value to f(0) [3]
Nearest result to 0 is 2
fn = [6, 18, 27, 51, 66, 198, 363]
n = [1, 3, 4, 6, 7, 13, 18]
searching for nearest value to f(1) [6]
Exact answer = 1
fn = [11, 18, 66, 102, 146, 198, 258, 291, 326]
n = [2, 3, 7, 9, 11, 13, 15, 16, 17]
searching for nearest value to f(0) [3]
Nearest result to 0 is 2
我找到了答案，这有点棘手 (hacky)。
但是我认为考虑到 Java 的 BinarySearch 在元素不是数组时返回 (-(insertion point) - 1) 这一事实，这是一个公平的游戏。
这个想法是通过例如取反来区分目标，所以在比较函数中，如果数字是负数，我们就知道它是目标（并取反），如果是正数，它就是一个数组元素，我们应该应用功能。
这是基于数组中没有负数的假设。如果有负数，则此方法不起作用。
这里是问题中示例的代码：
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
}
}