python - 查找区间索引的有效方法

Question

我正在用 Python 编写样条类。计算样条插值的方法需要最近的 x 个数据点的索引。目前的简化版本如下所示:

def evaluate(x):
    for ii in range(N): # N = len(x_data)
        if x_data[ii] <= x <= x_data[ii+1]:
            return calc(x,ii)

因此它遍历 x_data 的列表点直到找到较低的索引 ii x 的区间谎言并在函数 calc 中使用它，执行样条插值。虽然功能正常，但对于大型 x_data 而言，这似乎效率低下。数组如果 x接近数据集的末尾。是否有更有效或更优雅的方法来执行相同的功能，而不需要迭代检查每个间隔？

备注:x_data可以假定这样排序 x_data[ii] < x_data[ii+1] , 但不一定等距。

Answer 1

这正是 https://docs.python.org/2/library/bisect.html 的二分法

from bisect import bisect
index = bisect(x_data,x)
#I dont think you actually need the value of the 2 closest but if you do here it is
point_less = x_data[index-1]  # note this will break if its index 0 so you probably want a special case for that
point_more = x_data[index]

closest_value = min([point_less,point_more],key=lambda y:abs(x-y))

或者你应该使用二进制搜索(事实上我很确定那是什么 bisect 在引擎盖下使用)......它应该是最坏的情况 O(log n)(假设你的输入数组是已经排序)