有没有办法避免对此进行线性搜索？

Question

我有一大堆具有起始编号和结束编号的对象.例如:

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

假设间隔彼此不重叠.我正在编写一个函数,它接受一个数字并找到(低,高)包含它的对象.说给出333,我想要列表中的第3个对象.

有没有什么方法可以尽可能有效地做到这一点,缺少线性搜索？我在考虑二元搜索,但在处理范围检查方面遇到了一些困难.

Answer 1

想想是否值得对数据进行排序.
如果您只想搜索几次,那么它不会 - 而且您无法避免线性搜索.搜索的总复杂程度将是O(n*k),n元素k的数量和搜索的数量.

如果您想要搜索很多次,那么您应首先排序,然后使用二进制搜索进行搜索.这将是O(nlogn)排序和O(klogn)搜索k次,所以你得到总和O((n+k)logn).

因此,只有在进行排序和搜索时才应该进行 k>=logn

PS你可以使用另一种方法进行排序和搜索,如其他答案中所提出的,在所有方面,结论仍然是:只有在这样做时才这样做k>=logn

Answer 2

首先，根本不清楚这里是否有必要进行二分搜索。当间隔数量较小时，线性搜索很可能会更快。

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

除了免责声明之外，二分搜索可以通过对间隔进行一次排序，然后重复使用该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]从函数中分解出来并在开始时只执行一次。