c# - 快速找到最近浮点值的数据结构

Question

如果我有一堆如下数据，我应该使用什么样的数据结构:

MyData
{
    float ValueA;
    float ValueB;
    object OtherInfo;
}

我需要快速找到所有满足这种条件的 MyData 实例:

0.5 <= ValueA <= 0.7    AND    0.2 <= ValueB <= 0.9

找到这些项目很简单，但我需要尽快完成。有没有适合这个的数据结构？我不介意用完额外的内存。

我目前的想法是有一个排序列表，按 ValueA 排序。然后我会进行二分搜索以找到第一个 ValueA >= 0.5 的项目，然后迭代直到我得到一个 ValueA > 0.7 的项目。对于每次迭代，我检查 ValueB 是否在 0.2 和 0.9 之间。我将所有匹配项放入我的输出数据集中。

有更好/更快的方法吗？

顺便说一句，我正在使用 C#。

Answer 1

安interval tree会满足你的需要。示例实现(我还没有测试过)at Codeplex .更多 here .

更新:区间树与相关结构线段树的比较在此处:What are the differences between segment trees, interval trees, binary indexed trees and range trees?