インデックスの効率的な検索方法

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嘘区間の下限インデックスiiを見つけ、スプライン補間を行う関数calc、であることを利用するまで、だから、x_data点のリストを反復処理しました。機能的である間に、xがデータセットの最後に近い場合、これは大型のx_dataアレイでは効率が悪いようです。同じ機能を実行するために、より効率的または優雅な方法があります。これは、すべての間隔を繰り返しチェックする必要はありませんか？

注：は、x_data[ii] < x_data[ii+1]のようにソートされていると想定できますが、必ずしも等間隔である必要はありません。

Answer 1

これはまさに二分すると、あなたがバイナリ検索を（フードの下での使用を二分何thatsの実際のイムでかなり確信して）使用する必要があります代わりに....それは最悪の場合O(log n)（あるべき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)) 

ためですあなたの入力配列が既にソートされていると仮定して）