Re: Need efficient search strategy in list of time intervals

On 31 Jul., 14:07, Roedy Green <see_webs...@xxxxxxxxxxxxxxxxxxxx>
wrote:
On Tue, 31 Jul 2007 11:18:55 -0000, lemmi <dlemmerm...@xxxxxxxxx>
wrote, quoted or indirectly quoted someone who said :

I have a list of time intervals ([long,long]). The list is sorted
based on the start times of the intervals. I now need a fast
algorithm, which takes a time span TS as input and returns the index
of the first time interval A in the list that is contained in the
given time span. The rendering engine of my UI framework will then
iterate over the list starting at the calculated index.

That sounds like a job for a binary search.
Seehttp://mindprod.com/jgloss/binarysearch.html

Binary search fails because of the fact that the time intervals can
overlap each other.

.

Relevant Pages

  • Re: Need efficient search strategy in list of time intervals
    ... algorithm, which takes a time span TS as input and returns the index ... iterate over the list starting at the calculated index. ... That sounds like a job for a binary search. ...
    (comp.lang.java.programmer)
  • Re: Need efficient search strategy in list of time intervals
    ... which takes a time span TS as input and returns the index ... The algorithm gets constantly called as part of a paintmethod so it ... and the you can do a binary search for the Instant. ... dependent on the data a little more, one long interval can cause a big ...
    (comp.lang.java.programmer)
  • Re: Need efficient search strategy in list of time intervals
    ... which takes a time span TS as input and returns the index ... iterate over the list starting at the calculated index. ... You should consider whether there is a better data structure than a list ...
    (comp.lang.java.programmer)