Enabling ranges if the list contains a number with in those ranges (Java)

Question

I have some custom ranges as below:

Range A 3-6

Range B 6-9

Range C 10-11

Range D 12-15

Range E 16-99 (All the ranges are inclusive)

I have a List in a sorted order (low to high). The ranges should be enabled if there is at least one number from the list that fits in the respective ranges

To solve this i have to iterate the list and check whether at least one number fits in the range:

for(Integer a:list) {
  if (new Range(3, 6).contains(a.intValue())) {
    available = true; //(for respective range)
    break;                  
  }
}

comparing each and every value of list to enable a range seems to be a performance to me. Is there any best solution for this??

I am having a Range object with following attributes

private String name;
private int min;
private int max;
private boolean available;

3&6 in above snippet is min & max of Range A

First, move out `new Range(3,6)` of the for loop, these doesn't overload the allocated memory, neither the garbage collector. — viticlick, Nov 10 '15 at 17:21

score 0 · Answer 1 · answered Nov 10 '15 at 14:32

Probably no need to do a contains() since it will do a search and the best search algorithm will be O(log n) (Binary Search)

Just need to do the comparison (assuming both ranges are inclusive)

if (min<= value && value <= max)

Which is a constant comparison O(1)

Since you will be doing at most for n ranges the overall running time will be O(n) instead of O(nlogn)

score 0 · Answer 2 · edited May 23 '17 at 11:59

Given that the ranges are sorted, and assuming that they do not overlap, you can run a binary search on them to find inclusion faster. Use Arrays.binarySearch overload that takes a custom Comparator<? super T>.

However, given that you have only five ranges to check, doing a binary search sounds like a premature optimization, which is very likely to be unnecessary.

If the number of ranges and ints is large, you may be able to find the ranges to be enabled in a single pass through the list if you are allowed to sort the integers. The idea is to apply an algorithm similar to merging sorted arrays. Start at the beginning of the list of ints and the list of ranges, and advance indexes in merge-like succession. When an int fits in a range, mark the range enabled, and skip all ints from the list until you hit the upper end of the range, or exhaust the list of ints, whichever comes first.

Enabling ranges if the list contains a number with in those ranges (Java)

2 Answers2