如何抽象出不在数据结构上的二分查找？

Question

我有一个 Java 程序，我发现我已经 hand-implemented 了 3 次二进制搜索算法。问题是这个搜索不是在 filled-out 数据结构上完成的；相反，它是通过调用计算量大的数值方法（因此使用二进制搜索；我正在尝试减少对该方法的调用次数）。方法 header(s) 看起来像：

double computeValue1 (Thing thing, int parameter, int seed)

此方法始终 return 是 0 和 1 之间的双精度值。该函数是单调递增的（seed 的较高值总是 return 较高的输出；因此二分查找是有道理）。我正在使用搜索来查找 seed 的值，该值 return 的值最接近 0.5（给定固定的 Thing 和 parameter）。

所以理想情况下，Java 中会有一些抽象的库方法，我可以用它来完成这个搜索，而不是在我的代码中写出细节。此外，我实际上对 3 种不同的评估方法有 3 次不同的时间（比如，computeValue1、computeValue2，然后是第 3 次，我在 parameter 上进行相同的搜索，同时保持Thing 和 seed 固定）。

什么是抽象出二分搜索的优雅方法，这样我就不会维护 3 种独立的搜索方法（一种围绕 3 种计算方法中的每一种），它们大部分都在做同样的事情？

Answer 1

只要搜索参数的数据类型相同（int 在你的情况下），你可以这样做：

public int binarySearch(double targetValue, int from, int to, Function<Integer, Integer> compute) {
    while (...) {
        int currentParameter = ...;
        int currentValue = compute.apply(currentParameter);
        ...
    }
}

在Java8:

中这样调用

int seed1 = binarySearch(0.42, 0, 1000, s -> computeValue1(someThing, someParameter, s));
int seed2 = binarySearch(0.42, 0, 1000, s -> computeValue2(someThing, someParameter, s));
int param = binarySearch(0.42, 0, 1000, p -> computeValue1(someThing, p, someSeed));

如果没有Java8，需要自己定义Function接口：

public interface Function<TParameter, TResult> {
    TResult apply(TParameter parameter);
}

并使用匿名内部调用搜索 class:

int seed1 = binarySearch(0.42, 0, 1000, new Function<Integer, Integer>() {
    public Integer apply(Integer parameter) {
        return computeValue1(someThing, someParameter, parameter));
    }
});

如何抽象出不在数据结构上的二分查找？

How to abstract a binary search that is not over a data structure?

java

search

abstraction

numerical-methods