java - 如何找到最接近目标输出 (Y) 的最佳函数输入整数 (X)？

Question

这个答案与 VBA 中的 Excel 宏有关，我正在寻找最佳解决方案。答案可以通过伪代码、Python、Java 或 Excel 兼容的 VBA 提供。该方法应该能够用 Excel VBA 编写。

如果您有替代解决方案(即 Haskell 中的函数式编程)，我也希望看到这一点，但这不是主要问题。

我有一个复杂的函数:y = function (x)，其中 x 是输入，y 是输出。 x 是一个整数 y 是 double 型(可以包含小数)

我知道 x 必须处于的目标范围，比如说 0 到 2000，或者 800 到 1800。 我也知道你应该是什么。

函数是一个计算量大的函数，应该尽可能少地计算。

我看不到函数的内容，或者它太复杂而无法分析。 该函数的输出是一条递增曲线。 IE。 x=2 > x=1 则 y(2) > y(1)

我需要找到 x 值，该值可以为我提供最接近已知 y 值的 y 值。

计算效率最高的方法是什么？

<小时/>

我想到将范围划分为 20 个区域并循环。循环将在第一个大于目标的 y 处停止。 IE。它将运行 2 到 20 次。然后我会转到精确单位(整数)并循环遍历这个子区域或子范围，这意味着最大调用次数为(起始范围/20 - 即，如果起始范围是 0 到 600)，那么函数将被调用 2 到 30 次。

有没有更好的方法来做到这一点，也许是递归的。 我好像错过了这里的船？

Answer 1

对于y值总是增加的函数，可以使用binary search快速缩小潜在值的范围。 Python 实现示例:

def binary_search(func, min_x, max_x, target_y):
    while max_x - min_x > 1:
        midpoint = (min_x + max_x) / 2
        if func(midpoint) > target_y:
            max_x = midpoint
        else:
            min_x = midpoint
    return min_x

print binary_search(lambda n: n**2, 0, 600, 300**2)

该算法具有对数效率。对于 0 到 600 的范围，它仅调用 func 十次；对于两倍大的范围，只有十一次。