Appropriate data structure for fast searching "between" pairs of longs

Question

I currently (conceptually) have:

IEnumerable<Tuple<long, long, Guid>>

given a long, I need to find the "corresponding" GUID.

the pairs of longs should never overlap, although there may be gaps between pairs, for example:

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

For every input long, there should be exactly 0 or 1 matching GUIDs.

so an input of 7, should return 366586BD-3980-4BD6-AFEB-45C19E8FC989

an input of 16 should return null

Update: I have about 90K pairs

How should I store this in-memory for fast searching?

Thanks

Answer 1

So long as they're stored in order, you can just do a binary search based on "start of range" vs candidate. Once you've found the entry with the highest "start of range" which is smaller than or equal to your target number, then either you've found an entry with the right GUID, or you've proved that you've hit a gap (because the entry with the highest smaller start of range has a lower end of range than your target).

You could potentially simplify the logic very slightly by making it a Dictionary<long, Guid?> and just record the start points, adding an entry with a null value for each gap. Then you just need to find the entry with the highest key which is less than or equal to your target number, and return the value.