java - 二进制优化搜索

Question

我正在尝试编写一个函数来优化使用二进制分割的函数。我的想法是，我可以将下限和上限传递给它进行测试，它会返回从函数返回“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 || !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;
}