Re: Need efficient search strategy in list of time intervals

On Tue, 31 Jul 2007 11:18:55 -0000, lemmi <dlemmermann@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.
See http://mindprod.com/jgloss/binarysearch.html

--
Roedy Green Canadian Mind Products
The Java Glossary
http://mindprod.com
.

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)
  • 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. ... might have to iterate over a long list of irrelevant objects anyway. ...
    (comp.lang.java.programmer)