找到有效的算法来计算最小索引 k，使得 $|f(k)-v|$ 最小

Question

问题：给定一个递增的函数 f、一个浮点 v 和一个正整数 n，在区间 [0, n) 中找到一个整数 k，使得 |f(k)-v|是最小值。利用 f 正在增加的事实！

我的想法是考虑第一个 k 使得 f(k) >= v，因为之后我们不必检查，因为函数正在增加。这应该返回 f 最小值所在的索引。

但是，当我实现代码时，它在某些情况下返回错误的答案。这是代码：

def f(x):
    '''
    (float) -> float
    f must be increasing
    '''
    return x**2

def find(v, n):
    '''
    (float, int) -> int
    Returns k in [0:n]
    such that |f(k) - v| is minimum
    '''
    
    min_index = 0
    
    for k in range(n):
        if f(k) >= v:
            min_index = k
            return min_index

    return -1  

对于 find(5, 10) 的情况，它返回错误的索引（应该是“2”，但它返回“3”）。但是，当我调用 find(2, 10) 时，它给出了正确的答案。

这里发生了什么？

观察：无法使用二分查找等搜索算法

谢谢你

Answer 1

f 正在增加。所以

|f(k)-v|

的最小值为

 f(k)-v=0

（或者如果 f(0)-v > 0 则最小值为 0）

因此找到

f(k-1)-v < 0

和

f(k)-v >= 0

所在的整数。
这可以通过二分搜索来完成。

最后你需要决定是否

|f(k-1)-v| < |f(k)-v|

并返回

k-1

或

k