CODEWITHSUNDEEP
javaalgorithmsearcharraylist
krsi
krsi

Reputation: 1115

Fastest way to get interval from sorted list?

Let's say there's the Element class with position property.

public class Element {

   private float position;

   public float getPosition() {
      return position;
   }

   public void setPosition(float position) {
      this.position = position;
   }
}

Also, there's the ArrayList<Element> elements holding elements with randomly assigned position values. Elements are then sorted ascending by position values.

Question: What is the fastest way of getting all elements within some position interval <a,b>, other then simply iterating through elements, like this:

for (Element element : elements) {
   if (element.getPosition() > a && element.getPosition() < b) {
      // Do something with an element.
   }
}

I assume there is a faster way, due to the assumption that the list is sorted.

Upvotes: 2

Views: 724

Answers (3)

assylias
assylias

Reputation: 328735

If all elements are unique (or you don't need to store duplicate elements), you can use a TreeSet which implements the NavigableSet interface:

TreeSet<Element> set = new TreeSet<>(new Comparator<Element> () {
    public int compare(Element e1, Element e2) {
        return Float.compare(e1.getPosition(), e2.getPosition());
    }
});

Set<Element> betweenAandB = set.subSet(a, false, b, false);

Upvotes: 3

Adam Stelmaszczyk
Adam Stelmaszczyk

Reputation: 19847

You can do it faster using two binary searches:

final int start = Collections.binarySearch(elements, a);
final int end = Collections.binarySearch(elements, b);
return elements.subList(start, end + 1);

Make sure your Element correctly implements Comparable interface:

public class Element implements Comparable {
    @Override
    public int compare(Element e1, Element e2) {
        return Float.compare(e1.getPosition(), e2.getPosition());
    }
}

Upvotes: 2

NPE
NPE

Reputation: 500693

Use binary search to find the start and the end of the range, and then iterate between them.

Upvotes: 6

Related Questions