假设我有一根棍子，我把它切成碎片。给定原始杆上的一个点，有没有办法在恒定时间内找出它属于哪一块？
例如：
|------------------|---------|---------------|
0.0 4.5 7.8532 9.123
给定一个位置：
^
|
8.005
我想得到3rd piece。
使用二进制搜索可以在 O(log n) 时间内轻松获得这样的答案，但是否可以在 O(1) 中完成？如果我以某种方式预处理“切割”位置？
如果您假设要查询的点是沿杆均匀随机选择的，那么您可以获得 EXPECTED 恒定时间解，而不会出现疯狂的内存爆炸，如下所示。如果您将杆分成 N 个等距的部分，其中 N 是您在杆中原始不规则间隔的部分的数量，然后为 N 个相等大小的部分中的每一个记录原始不规则部分中的哪一个重叠，然后要进行查询，您首先只需获取查询点并进行简单的四舍五入以找出它所在的等间距片段，然后使用该索引查找哪些原始片段与等间距片段相交，并且然后检查每个相交的原始段以查看该段是否包含您的点（如果您想确保最坏情况下的性能仍然是对数，则可以使用二进制搜索）。
预期 O(1) 运行时间的证明：
当您计算原始 N 个不规则段和我建议构建的 N 个等距段之间的交集对总数时，总数不超过 2*(N+1) （因为如果您对所有端点进行排序在所有规则和不规则段中，总是可以将新的交叉点对充电到定义规则或不规则段的端点之一）。因此，您有最多 2(N+1) 个不规则段的多组，以某种方式分布在它们相交的 N 个规则段中。常规段之间交点的实际分布无关紧要。当您有一个统一的查询点并计算与包含查询点的常规段相交的不规则段的预期数量时，
使用基于比较的算法，你不会比 lg n 做得更好。将正 IEEE 浮点数的 31 个无符号位重新解释为 31 位整数是一种保序转换，因此尝试和 van Emde Boas 树都是可选的。我会先引导你进行三级尝试。
对于任意切割和精度，不是真的，您必须将位置与各种起点或终点进行比较。
但是，如果您只是在谈论少量削减，那么性能应该不是问题。
例如，即使有十个段，您也只有九个比较，而不是大量的计算。
当然，您始终可以将情况转换为多项式公式（例如ax^4 + bx^3 +cx^2 + dx + e），使用联立方程生成，这将为您提供一个段，但最高功率往往会随着段数的增加而上升，因此它不一定像简单的检查那样有效。
您可以为每个位置分配一个整数，然后将其用作查找表的索引，这将为您提供恒定时间的查找。如果你的棍子很短，而且你不把它切成几分之一毫米长的碎片，这很容易。如果你能得到这样的近似值，那将是我要走的路。
有一种增强的方法可以进一步概括这一点。在查找表的每个元素中，您将中间位置和段 ID 存储在左侧和右侧。这使得一次查找 (O(1)) 加上一次比较 (O(1))。缺点是查找表必须非常大，以至于在同一个表元素的范围内不能有超过两个不同的段。同样，这取决于您的要求和输入数据是否有效。