How to get the special value by the given value in a region?

Question

The values are match with the regions,

0 -> [0,60)

100 -> [60,120)

200 -> [120,180)

...

If I have a value 160, the program should return 200, because 160 is in (120, 180).

Is there any fast way to do this ?

It would be better to use the Java to describe.

Thanks.

UPDATE:

1.Maybe there are a large of resulting labels, like this:

0, 1, 2 , ... i ..., (i++)

2.The range of regions aren't always increase by 60.

[0, 60)

[60, 100)

...

Answer 1

With regions of equal length you could specify the result values that correspond to the regions in an array and calculate the array index based on the input value like this:

public class Example {
    private static final int[] MAPPING = {0, 100, 200};
    private static final int REGION_LENGTH = 60;

    public static int encode(int value) {
        // TODO apply range check to avoid ArrayIndexOutOfBounds
        return MAPPING[(value / REGION_LENGTH)];
    }

    public static void main(String[] args) {
        System.out.println(encode(160)); // prints 200
    }
}

Answer 2

use a binary search tree (or just an array) .
Search on the basis of first value of the interval , i.e value <= x .
Now

if( `end` of `interval > x`)   
        you got the interval   
 else 
    no interval contains x.  

Time complexity : O(log N).

Answer 3

Store the right ends of the regions. Then use a binary search to find the index of the lowest right end that's greater than the input value. Print/return the special value of that index.

public static int getSpecialValue(int inputValue, int specialValue[], int rightIndex[]) {

    int hi = rightIndex.length - 1, low = 0; // N = number of  regions

    while( hi >= low ) {
        int mid = (hi + low)/2;

        if( rightIndex[mid] > inputValue) {
            hi  = mid - 1;
        } else {
            low = mid + 1;
        }
    }

    return specialValue[hi];
}

Runtime Analysis: O(lg(N)), where N = number of regions.

If the regions always gets increased by 60 then you can follow the previous answers which takes O(1) runtime.

If the regions bounds are small (less than 1 million or so), you can preprocess the output in O(R) time, where R is the right index of the rightmost region and then answer each query in O(1) time.

Answer 4

desValue=((Inputvalue)/60)*100;

Inputvalue should be an Integer.