使用自定义函数的Java二元搜索

Question

在 Java 中是否可以对元素的函数而不是元素本身运行二元搜索？

换句话说，对 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) 递增。

Answer 1

是的，这是可能的。根据文档:

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.

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

其工作原理如下:

• 生成 list 1 到 20 的值。然后调用 n
• 创建一个 lambda，fn应用于每个n。
• 创建 Comparator<Integer> comp它使用 fn用于比较
• 使用list调用binarySort , n ，和comp
• 使用返回的索引查找最近的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