在长的排序列表中查找前后值

Question

在一个很长的已排序列表中，寻找一个数字（比如12.31）最快的方法是什么？如果找不到这个确切的数字，我还想得到它前面和后面的值（比如在下面的列表中，前面是11.12，后面是12.03）。
非常感谢！

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

Answer 1

如果你的列表是像你举的例子那样排好序的，我想用二分查找会是最快的方式。

Answer 2

指数搜索（也叫做跳跃搜索）在处理非常长的列表时，比普通的二分搜索要更有效。它的基本思路是从位置0开始，逐步向前扫描，每次增加步长，直到超过了要找的答案。到那时，就可以在最后两步形成的范围内进行二分搜索。如果还是没有找到这个元素，那么最后一次的尝试会指向最接近的元素。

你可以看看这个链接：信息检索的基本技术。里面提供了伪代码算法，并讨论了它与二分搜索的复杂度对比。

Answer 3

最快的方法可能是使用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