CODEWITHSUNDEEP
javahashmap
user201411
user201411

Reputation: 254

Return key when value in range

I have a large data set where values are non-overlapping ranges that are sorted in increasing order. There are holes between ranges and keys (type is long) can be assigned to multiple ranges:

[100,300] K1
[310,400] K1
[401,600] K2
[650,1000] K3
...

I need to find a key for a given value. If value doesn't belong to any range, I should return 0.

My approach was to build 

NavigableMap<Long, Range> map = new TreeMap<>();

and then

map.put(K1, new Range(100,300);
...

That results in a quite large map that is sorted by keys. This is not what I want since I would prefer to have a map that is sorted by range values so that I can easily conduct binary search. My problem is that I don't know how to use this map to find key for a given value. For example, value 101 should return K1, 500 should return K2, 301 should return 0. Is there any way to achieve what I want using NavigableMap or am I using the wrong approach?

Upvotes: 3

Views: 176

Answers (3)

Ken Bekov
Ken Bekov

Reputation: 14015

I believe, Map is not needed at all. You can just implement Comparable interface in Range class, and do the binary search in sorted list:

public class Range implements Comparable<Range>{

    private int start;
    private int end;

    public Range(int start, int end){
        this.start = start;
        this.end = end;
    }

    public int compareTo(Range range) {
        if(this.start<range.start) return -1;
        if(this.start>range.start) return 1;
        if(this.start==range.start){
            if(this.end<range.end) return -1;
            if(this.end>range.end) return 1;
        }
        return 0;
    }

    //... getters for fields
}

public class RangeBianrySearch{

    public static Range findRangeFor(int value, List<Range> rangeList) {
        return findRange(value, rangeList, 0, rangeList.size()-1);
    }

    private static Range findRangeFor(int value, List<Range> rangeList, int start, int end) {

        if(end<0 || start==rangeList.size()) return null;

        int index;
        index = start+(end-start)/2;    
        Range range = rangeList.get(index);

        if(start!=end){
            if(range.getStart()>value){
                return findRangeFor(value, rangeList, start, index-1);
            }else
            if(range.getEnd()<value){
                return findRangeFor(value, rangeList, index+1, end);
            }
        }

        if(range.getStart()<=value && range.getEnd()>=value){
            return range;
        }
        return null;
    }  
}

Usage:

List<Range> rangeList = new ArrayList<Range>();
rangeList.add(new Range(1,100));
rangeList.add(new Range(101,200));
rangeList.add(new Range(250,301));
//etc...
Collection.sort(rangeList); //important

Range range = RangeBianrySearch.findRangeFor(115);

Upvotes: 0

smttsp
smttsp

Reputation: 4191

It may be a bit dummy but might work.

Create a type having min-max-assign (e.g. [100,300, K1]) values. Then sort them based on their min values.

If you search for a min value, then binary search will return the position of it (say x), otherwise, it will return -index_to_be_inserted - 1. Then you can check if your value is in the range.

For example, 

[100,300] K1
[310,400] K1
[401,600] K2
[650,1000] K3

Your arraylist will be 100 (300, 'K1'), 310 (400, 'K1'), 401 (600, 'K2'), 650 (1000, 'K3').

If you search for 101 to 309, binary search result will be -1(x). Check the max value in the index -x-1 = -(-1)-1 = 0. If you searched 101 then 101<300 and you will return K1, if you searched for 301, you will return 0.

I don't claim this is the best way but it is a way that works with O(log_n)

Upvotes: 0

Jim Garrison
Jim Garrison

Reputation: 86774

Since you have stated the ranges cannot overlap but may have gaps, you should use a NavigableMap<Range,Long> with a Range representation that uses only the lower bound of the range for the hashCode and equals implementations.

Note that I have reversed the order of the generic types in the NavigableMap from what you show in your code sample.

To search for a value you want the largest entry (i.e. the entry with the largest lower bound) that is less than the search key.

Conversely, if you used the upper bound in the Range object, you'd want the smallest entry larger than the search key.

After you find the appropriate Map entry you have to double check that the key value is actually within range, due to the possible gaps.

Upvotes: 1

Related Questions