二进制优化搜索

Question

我正在尝试编写一个函数来优化使用二进制细分的函数。我的想法是，我可以将下限和上限传递给它进行测试，它将 return 函数中 returns 'true' 的 n 的最低值。

public interface BinaryTest {
    boolean test(int n);
}

/**
 * Returns the smallest int in the set lower <= n <= upper that returns true for
 * {@link BinaryTest#test(int)}. If a value 'n' returns true, then any value
 * > 'n' will also return true.
 *
 * If none of the values return true, return -1.
 */
int optimizeSmallest(int lower, int upper, BinaryTest testFunction) {
    // ???
}

虽然二分查找的例子很常见，但这种模式更难找到，而且我觉得很容易以差一错误告终。

optimizeSmallest 函数会是什么样子？

简单测试用例：

    for (int i = 0; i < 10; i++) {
        int j = i;
        int r = BinarySearch.optimizeSmallest(0, 10, (n) -> {
            return n > j;
        });

        assertEquals(i + 1, r);
    }

Answer 1

尝试：

int optimizeSmallest(int lower, int upper, BinaryTest testFunction) {
    if(lower >= upper) {
        return upper;
    }
    int mid = (low + high) >>> 1;
    return testFunction.test(mid) ? optimizeSmallest(lower, mid, testFunction) 
        : optimizeSmallest(mid, upper, testFunction);
}

Answer 2

int optimizeSmallest(int lower, int upper, BinaryTest testFunction) {
    if (lower > upper || !testFunction.test(upper)) {
        return -1;
    }
    while (lower != upper) {
        int middle = (lower + upper) / 2;
        if (testFunction.test(middle)) {
            upper = middle;
        } else {
            lower = middle + 1;
        }
    }
    return lower;
}

Answer 3

这不是最优的（在某些情况下它会第二次测试最终值），但似乎适用于我抛出的所有测试用例。我会把它留在这里，直到有人发布比这个更好的答案。

public static int optimizeSmallest(int lower, int upper, BinaryTest testFunction) {
    while (lower < upper) {
        int mid = (lower + upper) >>> 1;

        if (testFunction.test(mid))
            upper = mid;
        else
            lower = mid + 1;
    }

    return testFunction.test(lower) ? lower : -1;
}

二进制优化搜索

Binary optimization search

java

optimization

binary-search