長いソートされたリストの前後の値を検索

Question

長いソートされたリストで数値（たとえば12.31）を検索し、その値の前と後の値を取得する最も速い方法は何でしょうか？値が見つかりません（例：下のリストの11.12と12.03）？
事前に感謝します。

long_list = [10.11, 11.12, 13.03, 14.2 .. 12345.67] 

Answer 1

最速はpythonでビルトインサポートを使用することが考えられます。ここでは、bisectモジュールについて考えています。以下は、値がリストにある場合は、辞書を使用してO（1）をすばやくチェックインしています。そうでない場合は、bisectを使用して、求められた値よりも小さい値と大きい値を検索します。 x=100.3ため

#!/usr/bin/env python 

import bisect 

def find_lt(a, x): 
    'Find rightmost value less than x' 
    i = bisect.bisect_left(a, x) 
    if i: 
     return a[i-1] 
    raise ValueError 

def find_gt(a, x): 
    'Find leftmost value greater than x' 
    i = bisect.bisect_right(a, x) 
    if i != len(a): 
     return a[i] 
    raise ValueError 

# First create a test-list (49996 items) 
i=1.0 
R=[1.0] 
D={} 
while i < 10000: 
    i+=0.2 
    i=round(i,2) 
    D[i]=True 
    R.append(i) 

# Locate a value, in this case 100.3 which is not in the list 
x=100.3 
if D.has_key(x): 
    print "found", x 
else: 
    print find_lt(R, x) 
    print find_gt(R, x) 

出力：

100.2 
100.4 

Answer 2

あなたのリストがあなたの例のようにソートされている場合、私はバイナリ検索が最も速いと思います。

Answer 3

リストが非常に長い場合、指数関数的検索（AKAギャロッピング検索）は普通のバイナリ検索よりも優れたパフォーマンスを発揮します。考えは、増加するステップでポジション0から前方にスキャンすることであり、この時点で答えがパスされるまで、最後の2つのステップによって形成された範囲に対してバイナリサーチが実行される。要素が見つからない場合、最後の試行は最も近い要素を指します。

Basic Techniques for information retrievalをご覧ください。擬似コードアルゴリズムが提供され、バイナリ検索に対する複雑さが議論されます。

Answer 4

li = [10.11, 11.12, 13.03, 14.2, 15.6, 15.8, 17.9, 12345.67] 

def searsh(x,li): 
    itli = iter(li) 
    a = itli.next() 
    if a==x: 
     return a 
    else: 
     while True: 
      b = itli.next() 
      if b==x: 
       return b 
      elif a<x<b: 
       return (a,b) 
      a = itli.next() 
      if a==x: 
       return a 
      elif b<x<a: 
       return (b,a) 


print searsh(13.5,li) 
print searsh(10.11,li) 
print searsh(50.3,li) 
print searsh(12345.67,li) 

結果も

(13.03, 14.2) 
10.11 
(17.9, 12345.67) 
12345.67 

：

def searsh(x,li): 
    a = li[0] 
    if a==x: 
     return a 
    else: 
     j = 0 
     while True: 
      j += 1 
      b = li[j] 
      if b==x: 
       return b 
      elif a<x<b: 
       return (a,b) 
      j += 1 
      a = li[j] 
      if a==x: 
       return a 
      elif b<x<a: 
       return (b,a)