有没有一种方法可以避免对此进行线性搜索

Question

我有一个很大的对象池，其中有起始编号和结束编号。例如：

(999, 2333, data) 
(0, 128, data) 
(235, 865, data)
...

假设间隔彼此不重叠。我正在写一个函数，它取一个数字并定位包含它的对象（低，高）。假设给定333，我想要列表中的第三个对象。

除了线性搜索之外，有什么方法可以尽可能高效地做到这一点吗？我在考虑二进制搜索，但在处理范围检查时遇到了一些困难。

Answer 1

思考是否值得对数据进行排序。
如果你只想搜索几次，那么它就不会——而且你无法避免线性搜索。搜索的总复杂度将是O(n*k)，其中n是元素的数量，k是搜索的数量。

如果你想搜索很多次，那么你应该先排序，然后使用二进制搜索。它将是O(nlogn)用于排序，O(klogn)用于搜索k次，所以您总共得到O((n+k)logn)。

因此，只有当k>=logn

p.S.您可以使用其他答案中提出的另一种方法进行排序和搜索，在所有方面，结论仍然是：只有在k>=logn

Answer 2

您可以使用平分模块：http://docs.python.org/library/bisect.html

您需要对数据进行一次排序，然后使用平分线：

import bisect
data=None
tuples=[(0, 128, None), (235, 865, None), (999, 2333, None)]
tuples.sort()
print tuples
print bisect.bisect(tuples, (-1,))   # 0
print bisect.bisect(tuples, (1,))    # 1
print bisect.bisect(tuples, (333,))  # 2
print bisect.bisect(tuples, (3333,)) # 3

Answer 3

如果搜索速度是最重要的，那么您可以创建一个查找表（正如S.Lott已经评论的那样）。这将占用O（r）内存（其中r是范围的大小）、O（r）预处理时间和O的（1）搜索时间。创建一个范围大小的数组，并用指向数据或null的指针填充每个元素。

lookup = {}
for low, high, data in source_ranges:
    for i in range(low,high): # or maybe high+1 if the ranges are inclusive
        lookup[i] = data

现在查找是琐碎的。

Answer 4

首先，二进制搜索在这里是否有必要还不清楚。当区间的数量很小时，线性搜索可能会更快。

如果您关心性能，那么谨慎的做法是对代码进行评测，并可能根据您的典型输入对这两种方法进行基准测试。

除免责声明外，二进制搜索可以通过对间隔进行一次排序，然后重复使用bisect模块进行搜索来实现：

import bisect
intervals = [(999, 2333, 'int1'), (0, 128, 'int2'), (235, 865, 'int3')]
intervals.sort()
def find_int(intervals, val):
   pos = bisect.bisect_left([interval[1] for interval in intervals], val)
   if pos < len(intervals) and val >= intervals[pos][0]:
      return intervals[pos]
   else:
      return None
print(find_int(intervals, 0))
print(find_int(intervals, 1))
print(find_int(intervals, 200))
print(find_int(intervals, 998))
print(find_int(intervals, 999))
print(find_int(intervals, 1000))
print(find_int(intervals, 2333))
print(find_int(intervals, 2334))

在上文中，我假设区间是不重叠的，并且区间包括其起点和终点。

最后，为了提高性能，可以考虑将[interval[1] for interval in intervals]从函数中分解出来，并在一开始只做一次。