python - 在长排序列表中搜索之前和之后的值

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 用于查找小于和大于查找值的值。

#!/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)

x=100.3 的输出:

100.2
100.4