Find Range in which value lies in Java

Question

Suppose, I have an unsorted array of ranges. For e.g

class CreditRange{
   long credits;
   int id;
}

Now I want to find, given credit count value belongs to which one of the CreditRange.

Possible Set<CreditRange> of values can be

CreditRange :{id:1,credits:0}
CreditRange :{id:2,credits:100}
CreditRange :{id:3,credits:500}
CreditRange :{id:4,credits:250}

Case 1 : Now when user enters Credits = 50, this range comparator should give answer as

CreditRange :{id:1,credits:0}

Case 2 : Now when user enters Credits = 300, this range comparator should give answer as

CreditRange :{id:4,credits:250}

Case 3 : Now when user enters Credits = 600, this range comparator should give answer as

CreditRange :{id:3,credits:500}

We can assume the ranges array takes ~1M and fits the memory. I am looking for an easy algorithm, which uses only standard JDK collections without any 3d-party libraries and special data structures, but works reasonably fast.

What would you suggest?

Answer 1

I guess, it's not the range you are talking about. Rather you want the largest element that is less than your passed element.

You can follow the below steps to solve the problem:

• First implement a Comparator for your class, which compares on the basis of credits
• Then, use a TreeSet, passing an instance of that comparator to it's constructor. It will sort the item inside it, as per the comparator.
• Then use TreeSet#floor(E) method to get the greatest element which is less than E, as per the comparator. Of course, you have to create an object of CreditRange to search. You can't just search for 300.

Demo code:

NavigableSet<Integer> set = new TreeSet<>();
set.add(0);   set.add(100);
set.add(250); set.add(500);

System.out.println(set.floor(50));  // 0
System.out.println(set.floor(300)); // 250

And please rename your class. It is not depicting the range in any manner. It should perhaps be better named as CreditBound as specified by Jon Skeet in comments.

Answer 2

As mentioned by Rohit, one easy method is to use TreeSet floor (another is to implement a a modified variant of Binary search. this is a more complete answer:

package test;

import java.util.TreeSet;

class CreditRange implements Comparable<CreditRange> {
  long credits;
  int id;

  public CreditRange(int id, long credits) {
    this.id = id;
    this.credits = credits;
  }

  public CreditRange(long credits) {
    this.id = -1;
    this.credits = credits;
  }

  @Override
  public int compareTo(CreditRange o) {
    return credits < o.credits ? -1 : credits > o.credits ? 1 : 0;
  }

  @Override
  public String toString() {
    return "id:" + id + ", credits:" + credits;
  }
}

public class Test {
  public static void main(String[] args) {
    TreeSet<CreditRange> set = new TreeSet<>();
    set.add(new CreditRange(1, 0));
    set.add(new CreditRange(2, 100));
    set.add(new CreditRange(3, 500));
    set.add(new CreditRange(4, 250));
    System.out.println(set.floor(new CreditRange(50)));
    System.out.println(set.floor(new CreditRange(300)));
    System.out.println(set.floor(new CreditRange(600)));
  }
}