优化寻找一个数字在哪些数对之间的方法？涉及到IT技术，这是一个问题标题。

Question

给定一条线上的区域列表：

regions = [(10,25), (18, 30), (45, 60), ...] # so on so forth, regions can be overlapping, of variable size, etc.

我想知道一个点 X 属于哪些区域：

x = 23
find_regions(regions, x) # ==> [(10, 25), (18, 30)]

我知道天真地（以及我的当前实现）我们可以只在O(n)时间内进行搜索，但一个拥有数千个区域和查找点的更加复杂的使用情况（实际上，这是促使我们研究比这更快的方法的原因）正当我们去寻找一种更快的途径：

regions = [(start, end) for (start, end) in regions if start < x and x < end]

我猜想有人之前已经解决了这个问题，但是我不确定最佳的解决方法。你有什么想法吗？

- zaczap

---

为什么 find_regions(regions, x) 会返回 [(10, 20), (22, 30)]？ - Bach

忘记将示例更新为原始定义（18, 30）。 - zaczap

我还是不明白。在什么意义上，23属于区间(10,20)？ - Bach

结果发现我把它搞砸了。 - zaczap

你需要在可能的区域列表中找到所有输入介于最小值和最大值之间的区域吗？这会增加计算负担 - 没有算法可以在不检查其上限的情况下排除范围，如果下限符合要求，反之亦然。我无法回答这个问题，除非说如果您具有单调递增的下限，则可以从二分搜索算法中受益，以找到可能符合条件的范围。但是，任何算法都需要定义正确的行为，当多个范围覆盖输入时。 - Peter DeGlopper

Answer 1

这正是区间树的设计目标。谷歌搜索Python interval tree会出现一个名为Banyan的现有库，尽管我无法保证其可靠性，并且它似乎没有得到积极开发。您也可以自己实现区间树。

从N个区间列表构建区间树的预处理时间为O（Nlog（N）），与其他答案不同的是，它只需要O（N）的空间，而不管区间重叠的程度如何。找出包含给定点的区间数量所需的时间为O（M+log（N）），其中M是包含该点的区间数。

PyPI页面中提取的Banyan区间树演示：

>>> t = SortedSet([(1, 3), (2, 4), (-2, 9)], updator = OverlappingIntervalsUpdator)
>>>
>>> print(t.overlap_point(-5))
[]
>>> print(t.overlap_point(5))
[(-2, 9)]
>>> print(t.overlap_point(3.5))
[(-2, 9), (2, 4)]
>>>
>>> print(t.overlap((-10, 10)))
[(-2, 9), (1, 3), (2, 4)]

- user2357112

Answer 2

我对您的列表推导式唯一的修改是将其改为generator，将比较缩短为start < x < end，并在需要仅一个时选择性地调用next()：

>>> regions = [(10,25), (18, 30), (45, 60)]
>>> x = 23
>>> next((start, end) for (start, end) in regions if start < x < end)
(18, 30)

请注意，您的比较表达式 start > x and x < end 中的符号 > 是反向的。应该是 start < x and x < end。这个修正已经包含在我的答案中了。

---

编辑：看到有关二分查找的评论和答案，让我意识到我当然是错误的，没有改进的空间。话虽如此，为了稍微改进比较和通过next()进行短路，我仍将保留这个答案。但是，与二分搜索相比，我的改进微不足道。

我已经使您的搜索线性更快。二分法是对数级别的。

- mhlester

Answer 3

如果区域重叠，只需对这些区域进行排序并执行二分查找。

如果区域重叠，对于每个重叠的区域，计算重叠区域列表并将其存储为列表。然后执行二分查找。

例如：(1,10),(5,15) 转换为

(1,4), (5,10), (11, 15)
  |       |        |
(1,10) (1,10)  (5,15)
          |
       (5,15) 

也就是说，将 (5,10) 连接到它所属的区域。

注意：这些只是提示，您需要做更多的工作。

- ElKamina

---

排序本身的时间复杂度是O(NlogN)，而他原本的想法是O(N)。但从长远来看，预排序的方法将会战胜 O(N^M) 的方法。 - thefourtheye

Answer 4

我建议你将所有内容拆分为不重叠的基本区间，以便每个基本区间要么完全覆盖给定区间，要么完全在其外部。 然后，您可以创建从基本区间到给定区间的映射。 由于基本区间不重叠，您可以使用二分搜索轻松地找到匹配项。 从那里，您可以查找映射到它的实际区间。

初始排序是O（N log N），构建映射是O（N），最终查找是O（log N），因为有二分搜索。 基本区间的数量小于2 * N。

这是一个粗略的实现。 不确定搜索点恰好击中结束区间的情况。

class IntervalFinder():
    elem_list = [] # the borders of the elementary interval
    elem_sets = [] # the actual intervals mapped to each elementary
    def __init__( self, intervals ):
        # sort the left ends
        a = sorted( intervals )
        # sort the right ends
        b = sorted( intervals, key=lambda x : x[1] )
        ia = 0 # index into a
        start = a[0][0] # the start of the elementary interval

        # the set of actual intervals covering the
        # current elementary
        current = set()
        for xb in b:
            while ia < len(a) and a[ia][0] < xb[1]:
                stop = a[ia][0]
                # an elementary interval ends here
                # because a new interval starts
                if stop > start:
                    self.elem_sets.append( set( current ) )
                    self.elem_list.append(start)
                    start = stop
                current.add( a[ia] )
                ia += 1

            if start < xb[1]:                    
                self.elem_sets.append(set(current))
                self.elem_list.append(start)
                start = xb[1]

            current.remove( xb )

        self.elem_sets.append(set())
        self.elem_list.append(start)


    def find( self, a ):
        k = bisect.bisect( self.elem_list, a ) - 1
        if k<0:
            return set()
        # if its exactly on the border
        # it belongs to both the right and the left
        if a == self.elem_list[k]: 
            h = set(self.elem_sets[k])
            return h.union( self.elem_sets[k-1] )
        else:
            return self.elem_sets[k]

intervals = [ ( 1, 10), (5, 15), (10, 20), (5, 30) ]

ifind = IntervalFinder(intervals)
for x in [0, 4,5,9,10,11, 20, 25, 30, 35]:
    print( x, ifind.find(x) )

- pentadecagon