我正在寻找最快的方法来确定一条线上的点是否在这条线的子集内。我得到一个整数点，我也有一个“列表”：
在此示例中，如果我的点的值为 5，那么我返回 true，因为它包含在一个区间中，对于 55 也是如此。如果我的点等于 1000，我也返回 true，因为它与点列表匹配。
我正在寻找一种快速的方法（比线性更快）来检查这种情况，而不必实例化尽可能多的整数（即，对于 1:1000 的间隔，我不想实例化 1000 个整数）。这可以在对数时间内完成吗？
谢谢
编辑：您可以认为预处理数据列表所花费的任何时间都等于 0，因为一旦处理了我的初始间隔，我需要将此测试应用于 10k 点
嗯，也许你可以使用区间或分段树：
如果您对整数范围进行了排序并且范围不重叠，则可以执行二进制搜索以在对数时间内找到正确的范围。
范围有什么限制吗？基于此，您可能会想出哈希函数来在恒定时间内进行搜索。但这取决于您的约束条件。
经过反思，我认为以下代码应该在对数时间内工作，不包括构建地图所需的时间：
enum pointType {
point,
open,
close
};
std::map<long int, pointType> mapPoints;
mapPoints.insert(std::pair<long int, pointType>(3, point));
//create the 5:10 interval:
mapPoints.insert(std::pair<long int, pointType>(5, open));
mapPoints.insert(std::pair<long int, pointType>(10, close));
int number = 4;
bool inside = false;
std::map<long int, pointType>::iterator it1 = mapPoints.lower_bound(number);
if(it1->first == number || it1->second == close) {
inside = true;
}
我认为只要地图以非重叠间隔正确填充，这应该可以工作
如果您不计算构建树所花费的时间（大多数树需要 n log n 或类似的时间来构建），您可以在给定树数据结构（我推荐 B 树）的亚线性时间内做到这一点。
如果您只有一个简单的列表，那么您不能做得比线性更好，因为在最坏的情况下，您可能必须检查所有点和间隔。
首先检查点的 hash_map。这就是简单的检查。
然后只需按第一个坐标排序间隔图，然后找到该点的 lower_bound。
然后检查您是否包含在返回的元素中。如果你不在那个，你就没有。
您可以使用布隆过滤器来测试一个点，看看它是否不在一个区间内，在线性 O(1) 时间内。如果它通过了该测试，您必须使用另一种方法，例如二进制搜索，以查看它是否肯定是间隔的一部分，在 O(log n) 时间内。