This may be a naive answer but I would treat it as a math problem. If the intervals are of a constant size then finding the appropriate interval is a matter of division. If the intervals are of variable length then I would fundge it. I would create another structure keyed by constant time intervals and have the value be a list of the appropriate variable length intervals. Find the position in the coarser constant length structure by math and then hand to a search routine to find the position in the variable length structure. Then I would only be searching through a small number for each time.

I hope I explained that OK :)

--
my $chainsaw = 'Perl';