递增函数下寻找使|f(k)-v|最小的k的算法问题排查

给定递增函数f、浮点数v和正整数n，需要在区间[0, n)中找到整数k，使得|f(k)-v|最小，要求利用f递增的特性。

当前实现的思路是找到第一个满足f(k)≥v的k，但代码在部分场景下出错：

• 调用find(5,10)时返回3，但正确结果应为2；
• 调用find(2,10)时结果符合预期。

要求不能使用二分搜索等算法，需排查问题并修正。当前代码如下：

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  

你的思路方向没问题，但忽略了递增函数的核心特性：当找到第一个f(k)≥v的k时，v必然落在f(k-1)和f(k)之间（k≠0时），此时必须比较k和k-1与v的差值，才能确定哪个点的距离更小。

以find(5,10)为例：

• f(2)=4 <5，f(3)=9 ≥5，你的代码直接返回3，但|4-5|=1远小于|9-5|=4，显然2才是正确结果。

另外代码还有两个逻辑错误：

1. 当所有f(k)都小于v时，应该返回n-1（因为函数递增，最后一个元素离v最近），而不是返回-1；
2. 初始的min_index=0完全没起到作用，循环里直接返回了第一个符合条件的k。

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
    '''
    if n == 0:
        return -1  # 题目规定n是正整数，此分支可作为边界防护
    
    closest_k = 0
    for k in range(1, n):
        current_val = f(k)
        # 找到第一个f(k)≥v的位置，对比k和k-1的差值
        if current_val >= v:
            prev_val = f(k-1)
            if abs(current_val - v) < abs(prev_val - v):
                closest_k = k
            else:
                closest_k = k-1
            return closest_k
        # 若当前值仍小于v，更新候选为当前k（递增特性下，后续值更大）
        closest_k = k
    
    # 所有f(k)都小于v，返回最后一个索引
    return closest_k

• 调用find(5,10)：对比f(2)=4和f(3)=9与5的差值，返回2，符合预期；
• 调用find(2,10)：对比f(1)=1和f(2)=4与2的差值，返回1（这才是真正的正确结果，原代码返回2其实是错误的）；
• 调用find(100,10)：所有f(k)中f(9)=81<100，返回9，正确。

内容的提问来源于stack exchange，提问作者Lucas