Implementation for Range search algorithm

Question

I would like to ask a question about the algorithm.

Suppose there are several segments.(segments number not fixed,maybe so longd)

example:

segment                  data range (data range not fixed)

**A                             0~10**

**B                             11~45**

**C                             46~49**

**D                             50~100**

**E                             101~105**

**F                             106~128**

If input → 99

I will get output ‘D’ from my program.

I will put this example implementation in java.

So, Do you have any way or algorithm to make the program execution time faster?

At least try to write some piece of code and then ask for help. — Punit, Sep 27 '17 at 07:42
If the ranges are always consecutive, as in your example, just use binary search. — Jordi Vermeulen, Sep 27 '17 at 07:46

score 0 · Answer 1 · answered Sep 27 '17 at 07:44

0

You can use Guava's Range. Create ranges, check (simple for loop) if your input is in range.

Guava's Range Tutorial

Ranges Explanation

Docs

answered Sep 27 '17 at 07:44

MicD

197
2
11

score 0 · Answer 2 · answered Sep 27 '17 at 07:49

0

You can use ConcurrentSkipListMap and add to map the range and values

answered Sep 27 '17 at 07:49

Ori Marko

56,308
23
131
233

score 0 · Answer 3 · answered Sep 27 '17 at 07:52

Assuming that your data ranges are both sorted and do not overlap, then you can try using a binary search style approach to this.

You can place the starting values of each range into an array:

[0, 11, 46, 50, 101, 106]

The correct starting value, if it exists, would have the following two properties:

It is less than 90
The adjacent value to the right is either greater than 90 or does not exist (e.g. if the start value were the last range in the array)

Searching for 90 is trivial in this case because we would immediately hit it. Let's say we wanted to find 20. We would take the following steps:

[0, 11, 46, 50, 101, 106]
Choose 50; fails because 50 > 20; go left
[0, 11, 46]
Choose 11; succeeds because 20 > 11 and 20 < 46

So this would yield the range 11-45, and we need one more check to make sure that 20 is within this range. In this case it is, but it doesn't have to be. The binary search approach described above only finds the best fit range, which doesn't necessarily have to contain the actual number.

score 0 · Answer 4 · answered Sep 27 '17 at 08:14

0

You could use an Interval Tree - I posted an implementation here some time ago.

An Interval Tree can handle overlapping ranges too.

answered Sep 27 '17 at 08:14

OldCurmudgeon

64,482
16
119
213

Implementation for Range search algorithm

4 Answers4