求递增函数最后一个负值的索引：寻求高效内置实现方案

嘿，这个场景太典型了！既然你的函数是严格递增的，那完全没必要傻乎乎遍历整个序列——直接用二分查找就搞定，而且Python本身就有现成的工具或者简单实现方式，完美适配你这种「函数计算耗时」的情况。

最优方案：用Python 3.10+的bisect模块（内置且简洁） #

从Python 3.10开始，bisect模块的bisect_left和bisect_right支持key参数，这简直为你的需求量身定做！因为你的x_range是递增的，函数f也是递增的，所以f(x)的结果序列也是有序的——我们只需要找到第一个让f(x) ≥ 0的索引，减一就是最后一个f(x) < 0的位置。

代码示例：

import bisect
import numpy as np

def f(x):
    # 这里模拟你的耗时计算，实际替换成你的业务逻辑
    # import time; time.sleep(60)
    return x - 7

x_range = np.linspace(-10, 10, num=1000)

# 找到第一个f(x) >= 0的索引
first_non_neg_idx = bisect.bisect_left(x_range, 0, key=lambda x: f(x))
# 最后一个f(x)为负的索引就是这个位置减一
last_neg_idx = first_non_neg_idx - 1

print(last_neg_idx)

这个方法的好处是：完全用内置实现，代码极简，而且二分查找只需要log2(n)次函数计算——比如n=1000的话，最多只需要10次f的调用，比遍历1000次快到飞起！

兼容旧Python版本：自定义二分查找（可结合初始猜测优化） #

如果你的Python版本低于3.10，没法用key参数，那自己写一个二分查找也超简单，还能用上你手里的初始猜测值来进一步缩小查找范围，减少计算次数：

import numpy as np

def f(x):
    # 模拟耗时计算
    # import time; time.sleep(60)
    return x - 7

x_range = np.linspace(-10, 10, num=1000)

def find_last_neg_index(x_range, f, initial_guess=None):
    low = 0
    high = len(x_range) - 1
    
    # 利用初始猜测缩小查找范围
    if initial_guess is not None:
        guess_val = f(x_range[initial_guess])
        if guess_val < 0:
            # 猜测位置的f值是负的，说明目标在右边，把low设为猜测值
            low = initial_guess
        else:
            # 猜测位置的f值非负，目标在左边，把high设为猜测值
            high = initial_guess
    
    last_neg_idx = -1
    while low <= high:
        mid = (low + high) // 2
        current_val = f(x_range[mid])
        if current_val < 0:
            # 当前位置是负的，记录下来，继续往右边找更大的索引
            last_neg_idx = mid
            low = mid + 1
        else:
            # 当前位置非负，往左边找
            high = mid - 1
    return last_neg_idx

# 使用示例，传入初始猜测值
last_neg_idx = find_last_neg_index(x_range, f, initial_guess=500)
print(last_neg_idx)

这个自定义函数不仅高效，还能通过初始猜测值跳过不必要的计算，非常适合你这种单次函数计算耗时的场景。

为什么这两种方法比遍历好？ #

原来的遍历是O(n)时间复杂度，n=1000就要调用1000次f；而二分查找是O(log n)，1000次的话只需要约10次调用——每次1分钟的话，直接从16小时降到10分钟，效率提升不是一点半点。

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