2

I have the following table:

block | start | end

1 | 1 | 4

2 | 5 | 9

3 | 10 | 20

4 | 21 | 50

..........

n | 1000 | 2000

When given a value to variable c i have to search which block contains c ( start < c < end ). For example when c = 1001, c is in block n. What data structure would be the most efficient?

jpe
  • 1,013
  • 6
  • 14
cldo
  • 1,735
  • 6
  • 21
  • 26
  • Can you re explain with an example? – Mustafa Jul 05 '12 at 14:55
  • thanks.example: c = 3. 1 c in block 1 (1,4) . c = 1001 (1000 < c < 2000) == > c in block n – cldo Jul 05 '12 at 14:57
  • Is the complete range always filled (ie 1-2000) and always in sequential order? – Ian Bishop Jul 05 '12 at 15:02
  • Yes. array are order but it is not sequential. Example list block is {(1,3) (6,9) ,(12,20)} – cldo Jul 05 '12 at 15:10
  • The question seems to be very similar to this: http://stackoverflow.com/questions/1580185/data-structure-for-quick-time-interval-look-up – jpe Jul 05 '12 at 19:58
  • Have you tried the interval tree answers cldo? If not, why not? If they were working, please accept one of the answers (using the V sign to the left of the answer). – Maarten Bodewes Aug 20 '12 at 21:14

5 Answers5

1

If the entire range of your integers is only 1..2000 you could think of your data as a table like this:

n   block
1   1
2   1
3   1
4   0
5   0
6   2
.
.
.

which you'd implement as a vector of 2000 elements. Simple look up of element n in the vector will tell you which block n is in (unless you've chosen to implement in a language with 0-based indices in which case element n tells you which block integer n+1 is in). Here I've used 0 to indicate 'no block'.

This trades space for time compared with some of the other answers here, but that's often an acceptable trade off.

High Performance Mark
  • 77,191
  • 7
  • 105
  • 161
1

An interval tree or segment tree would work. Essentially, you'd be able to binary search through the intervals to find which contains the point in question. Since Segment Tree's are better at stabbing queries, it'd be the first I'd try.

If you are using Java, I've implemented them both in java before. You can find the interval tree here and the segment tree here.

Justin
  • 4,196
  • 4
  • 24
  • 48
1

An interval tree would be fairly appropriate for this problem, I think. It's certainly a lot harder to implement than a table, and if you don't need to dynamically add your blocks, I would suggest just keeping with a table and using a simple binary search for finding your blocks. That should achieve the same efficiency as the interval tree without all the terrible coding pains (as long as you don't have to add intervals).

Dylan M.
  • 116
  • 1
  • 7
0

I'm not sure what you are asking for

I believe there are many ways of implementing such blocks, personnaly I would have an ordrer list containing the end of each block and run through it until the end is greater than the value, the index giving me the number of block

Amxx
  • 3,020
  • 2
  • 24
  • 45
0

For this particular example you can store start in an array (which is in sorted order) and do binary search to get to the appropriate block.

Edit explaining the example:

In the start array you have 1,5,10,21,1000 so for c=3 you know it is in block 1 because 5 is the start index of block 2.

For some reason if you also want to look at end then you can store that in another array and access end of a start from the index that you got from binary search.

user1168577
  • 1,863
  • 11
  • 14
  • Thanks.i am sorry my example is not exactly.If my list block is {(1,3) (6,9) (13,20) ... } In this case i cant not use binary search.Because if value = 5 it have to return null. – cldo Jul 05 '12 at 15:07
  • Not sure if you looked at my latest edit where I talk about storing end so you will get index 0 for 5 and check 0th element in end which is less than 5 so you return not found. – user1168577 Jul 05 '12 at 15:09