时间戳

首页 > 解决方案 > 使用自定义函数的 Java binarySearch

java - 使用自定义函数的 Java binarySearch

问题描述

是否可以在 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)

另请注意“平方”只是一个例子，它有一个反向平方根。但一般假设没有反向功能。即我们想在元素上应用函数进行二分搜索。

另一个注意事项：假设数组已排序，并且 f(i) 正在增加。

标签： javafunction-pointersbinary-search

解决方案

对的，这是可能的。根据文档：

该方法返回搜索键的索引，如果它包含在列表中；否则，
(-(insertion point) - 1)。插入点定义为将键插入列表的点：第一个元素的索引大于键，或者list.size()列表中的所有元素都小于指定的键。请注意，这保证了当且仅当找到键时，返回值将 >= 0。

因此，通过调整返回的索引，您可以获得最接近找到所需值的位置的下一个值（甚至上一个值）。

这工作如下：

  • 生成一个list1 到 20 的值。然后调用n
  • 创建一个 lambda，fn以应用于每个 n。
  • 创建一个Comparator<Integer> comp用于fn比较的
  • list使用、n和调用 binarySortcomp
  • 使用返回的索引找到最近n的f(n)

这是一个返回最接近的值的示例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

推荐阅读