1

並べ替えられたリストから最小値と最大値の間にある (または等しい) 要素を抽出するために、平均ケース パフォーマンスが O(log(N)) のアルゴリズムを探しています。

問題は、最小値と最大値が実際にはリストにないか、繰り返されていない可能性があるため、バイナリ検索が実行されないことです。三分探索のほうが自分の求めるものに近そうですが、今のところ三分探索に基づいて私が見ていることを行う関数を作成できていません。

たとえば、次のように入力します。

list=[1,2,3,4,5,6,7], min=3, max=6

[3,4,5,6] を返す必要があります。同じく、

list=[500,757,2412,10000,123123], min = 600, max = 5000

[757,2412] を返す必要があります。

これは、以下を使用して Python で効率的に行うこともできます。

def withinRange(values,min,max):
   return [val for val in sorted(values) if val <= max and val >= min]

操作は十分に呼び出されるため、O(log(N)) が非常に優先され、並べ替えは 1 回だけ実行されます。

4

1 に答える 1

2

これはうまくいくようです：

>>> import bisect
>>> def bin_slice(L, min, max):
...     i = bisect.bisect_left(L, min)
...     j = bisect.bisect(L, max)
...     return L[i:j]
... 
>>> bin_slice([1,2,3,4,5,6,7,8,9], 3, 6)
[3, 4, 5, 6]
>>> bin_slice([500,757,2412,10000,123123], 600, 5000)
[757, 2412]

複雑さは、O(log(N)) である 2log(N) のようなものです。また、純粋な python で記述できるものよりも高速なbisectC 実装を使用する可能性があるため、比較が少し少なくても、純粋な python ソリューションはおそらく遅くなることに注意してください。bisect

パラメータをにj渡すための検索をわずかに最適化できます。lobisect

j = bisect.bisect(L, max, i)
于 2012-11-22T07:42:13.997 に答える