Find the range in which a value is in Java

Question

Suppose I have an unsorted array of ranges. For example,

class CreditRange{ long credits; int id; } 

Now I want to find if the value of the credit account belongs to one of CreditRange.

Possible values ​​for Set<CreditRange> may 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 the user enters Credits = 50, this range comparator should give answer as

CreditRange :{id:1,credits:0}

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

CreditRange :{id:4,credits:250}

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

CreditRange :{id:3,credits:500}

We can assume that the range array accepts ~ 1M and is suitable for memory. I am looking for a simple algorithm that uses only standard JDK collections without any 3d party libraries and special data structures, but works fast enough.

What would you suggest?

Answer 1

I think this is not the range you are talking about. Most likely you need the largest element that is smaller than your passed element.

To solve the problem, you can follow these steps:

• First we will implement Comparator for your class, which is compared on the basis of credits.
• Then use the TreeSet , passing an instance of this comparator to the constructor. It will sort the element inside it, according to the comparator.
• Then use the TreeSet#floor(E) method to get the largest element that is less than E , according to the comparator. Of course, you need to create a CreditRange object to search. You can't just search 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 rename your class. It does not depict the range in any way. It’s probably better to call it CreditBound , as John Skeet pointed out in the comments.

Answer 2

As Rohit already mentioned, one simple way is to use the bottom of the TreeSet (the other is to implement a modified version of the 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))); } }