# Time-indexed "array" of time spans

I have a list of objects that have durations,

``````ProcedurePart
Start: double
Stop: double
Instructions: string
``````

they occur sequentially after each other:

``````stepOne                   stepTwo                      stepThree
Start: 0.0                Start: 1.56                  Start: 5.443
Stop: 1.56                Stop: 5.443                  Stop: 10.9
"Take the dinglebop"      "Smooth it with shleem"      "Push it through the gru...
``````

I want to pull out items using a timestamp, the item retrieved should be the step within which that timestamp falls.

E.g., for the above sequence:

``````sequence[0.0] = stepOne
sequence[1.0] = stepOne
sequence[1.56] = stepTwo
sequence[2.578281] = stepTwo
sequence[10.0] = stepThree
``````

The precision is only limited by the data-type (C#'s `double`), and because times are continuous I can't create a look-up table using all possible discrete input values. Is there a data structure that can store this sequence and allow for anything better than O(log(N)) look-up times (better than binary search)?

• What about using a normalized `DateTime` instead of `double`, maybe with a custom comparator? Commented Aug 25, 2020 at 12:36
• @πάνταῥεῖ how will that allow for faster than O(logN) look up? Commented Aug 25, 2020 at 12:58
• Why do you need better than binary search algorithm? How many steps are you expecting? Billions? And even in such case, having 5 000 000 000 steps, binary search would need ~30 iterations at worst, which is pretty much nothing.
– Andy
Commented Aug 25, 2020 at 12:59
• @Andy I don't expect that many steps, but I will be "indexing" (using different times) lots and lots of times. 30 iterations for billions is a good point though, I honestly hadn't thought of it. I was just excited by the theory behind a possible fast algorithm for this. Commented Aug 25, 2020 at 13:16
• @Kain0_0 "time step cells" .... theoretically infinite memory usage? Commented Aug 26, 2020 at 9:59