适当的数据结构,用于快速搜索"两对"之间的长度

Question

我目前(概念上)有:

IEnumerable<Tuple<long, long, Guid>>

给定一个long,我需要找到"对应的" GUID.

longs 对不应重叠,尽管对之间可能存在间隙,例如:

1, 10, 366586BD-3980-4BD6-AFEB-45C19E8FC989
11, 15, 920EA34B-246B-41B0-92AF-D03E0AAA2692
20, 30, 07F9ED50-4FC7-431F-A9E6-783B87B78D0C

对于每个输入long,应该有完全匹配0或1匹配的GUIDs.

所以输入7,应该返回366586BD-3980-4BD6-AFEB-45C19E8FC989

输入16应该返回null

更新:我有大约90K对

我应该如何将其存储在内存中以便快速搜索？

谢谢

Answer 1

只要它们按顺序存储,你就可以根据"范围的开始"和候选者进行二进制搜索.一旦找到具有最大"范围开始"的条目,该条目小于或等于您的目标数字,那么您已经找到了具有正确GUID的条目,或者您已经证明您已经命中了差距(因为范围最高较小开始进入具有较低端的范围比你的目标).

您可以通过使其成为a Dictionary<long, Guid?>并且仅记录起始点来简单地简化逻辑,为每个间隙添加具有空值的条目.然后,您只需要找到最高键小于或等于目标数的条目,然后返回该值.