I have a list of objects that have durations,

  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? Aug 25 '20 at 12:36
  • @πάνταῥεῖ how will that allow for faster than O(logN) look up? Aug 25 '20 at 12:58
  • 4
    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
    Aug 25 '20 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. Aug 25 '20 at 13:16
  • 1
    @Kain0_0 "time step cells" .... theoretically infinite memory usage? Aug 26 '20 at 9:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.