如何找出一个点是否在一组区间内？

我正在寻找最快的方法来决定一条线上的一个点是否在该线的子集内。 给我一个整数Point，我也有一个“列表”：

1. 点，由整数（3,10,1000等）表示
2. 间隔，我用2个整数代表（2:10是从2到10的所有整数，50：60等）

在这个例子中，如果我的点的值是5，那么我返回true，因为它包含在一个区间中，相同的是55.如果我的点等于1000，我也返回true，因为它匹配点列表。

我正在寻找一种快速的方法（比线性更快）来检查这种情况，而不必像可能的点那样实现尽可能多的整数（即，对于1：1000的间隔，我不想实现1000个整数）。 这可以在对数时间内完成吗？

谢谢

编辑：你可以认为任何时候预处理数据列表等于0，因为一旦我的初始间隔被处理，我需要将这个测试应用到10k点

Answer 1

嗯，也许你可以使用间隔或段树：

• http://en.wikipedia.org/wiki/Segment_tree
• http://en.wikipedia.org/wiki/Interval_tree

Answer 2

如果您对整数范围进行了排序并且范围不重叠，则可以执行二进制搜索以在对数时间内找到正确的范围。

范围是否有任何限制？ 基于此，你可以提出散列函数来恒定搜索。 但这取决于你的约束方式。

Answer 3

反思之后，我认为以下代码应该以对数时间工作，不包括构建映射所需的时间：

enum pointType { point, open, close }; std::map mapPoints; mapPoints.insert(std::pair(3, point)); //create the 5:10 interval: mapPoints.insert(std::pair(5, open)); mapPoints.insert(std::pair(10, close)); int number = 4; bool inside = false; std::map::iterator it1 = mapPoints.lower_bound(number); if(it1->first == number || it1->second == close) { inside = true; } 

我认为只要地图以非重叠的间隔正确填充，这就应该有效

Answer 4

首先检查点的hash_map。 这是简单的检查。

然后，只需按第一个坐标排序间隔图，然后找到该点的lower_bound。

然后检查您是否包含在返回的元素中。 如果你不在，那你就不在。

Answer 5

您可以在次线性时间内执行此操作GIVEN树数据结构（我建议使用B树），如果您不计算构建树所花费的时间（大多数树需要n log n或类似的时间来构建）。

如果你只有一个简单的列表，那么你不能比线性更好，因为在最坏的情况下你可能需要检查所有的点和间隔。

Answer 6

您可以使用布隆filter测试一个点，并在线性O（1）时间内查看它是否在一个区间内。 如果它通过了该测试，则必须使用其他方法（如二进制搜索）来查看它是否是O（log n）时间内的间隔的一部分。