# Algorithm for dividing a range into ranges and then finding which range a number belongs to

Having

• a minimum
• a maximum
• number of ranges
• a value between minimum and maximum

I'm trying to come up with a method, or two, which would calculate which range the provided value belongs to.

For min=1, max = 10, number of ranges=5 the ranges would be [1,2],[3,4],[5,6],[7,8],[9-10]

The other method would behave like shown below:

• method(1)->[1-2]
• method(2)->[1-2]
• method(3)->[3-4]
• method(4)->[3-4]
• method(5)->[5-6]
• method(6)->[5-6]
• method(7)->[7-8]
• method(8)->[7-8]
• method(9)->[9-10]
• method(10)->[9-10]

This would be used for generating a legend for a map where the size of the marker depends on the range a value belongs to.

I wonder if there is a nice algorithmic solution for this.

The numbers I work with are integers.

Edit:

Another example:

For min=1, max = 3, number of ranges=2 the ranges would be

a) [1-2],[3-3]

or

b) [1-1],[2-3]

The other method would behave like shown below:

a)

• method(1)->[1-2]
• method(2)->[1-2]
• method(3)->[3-3]

or b)

• method(1)->[1-1]
• method(2)->[2-3]
• method(3)->[2-3]

I don't have a preference for a) or b).

• Basically, you want division. If the ratio between number and range size is smaller than 1, it goes into the first bin, etc. (OK, if your range doesn't start from 0, then you have to subtract the offset from both first, but that's it.) – Kilian Foth Feb 20 '13 at 8:48
• Are the ranges necessarily of equal length? Could I choose the ranges [1-3], [4-10], or is that not an option? If they're of equal length, then this is a pretty simple division problem, as Killian said above. If not, you need actual searching of ranges - playing with a binary tree would be an obvious option. – Standback Feb 20 '13 at 10:28
• Yes, I'm after ranges of equal length when possible (for range 1-3 and number of ranges 2 it would not be possible and it's ok). – tymtam Feb 22 '13 at 5:31

Here's what I would do:

First start with an array the size of number of ranges to keep track of the length of each range. Let's call this `bucket_sizes[number_of_ranges]`

1. Initialize the size of each bucket with the highest evenly possible length: `(max-min+1)/number_of_ranges` (integer division)
2. Then, find the surplus that couldn't fit evenly in each bucket, `(max-min+1) % number_of_ranges` (remainder from integer division)
3. Distribute the surplus as evenly as possible between each bucket (start at index 0, add 1 to each bucket while subtracting 1 from surplus. If index wraps to end of bucket_size array, start from index 0 again and continue until surplus is 0).

Now that we know the size of each bucket, we can generate the ranges:

``````for (i=0, k=min; i<number_of_ranges; i++) {
ranges[i].lo = k;
ranges[i].hi = k+bucket_sizes[i]-1;
k += bucket_sizes[i];
}
``````

To find the range of a specific number, simply iterate the `ranges` array and match the range where `ranges[i].lo <= number <= ranges[i].hi`.

Here is the full source code that I used to test this out (it's written in C):

``````#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

struct range
{
int lo;
int hi;
};

int generate_ranges(int min, int max, int number_of_ranges, struct range ranges[])
{
int i;
int bucket_sizes[number_of_ranges];

int even_length = (max-min+1)/number_of_ranges;
for(i=0; i<number_of_ranges; ++i)
bucket_sizes[i] = even_length;

/* distribute surplus as evenly as possible across buckets */
int surplus = (max-min+1)%number_of_ranges;
for(i=0; surplus>0; --surplus, i=(i+1)%number_of_ranges)
bucket_sizes[i] += 1;

int n=0, k=min;
for(i=0; i<number_of_ranges && k<=max; ++i, ++n){
ranges[i].lo=k;
ranges[i].hi=k+bucket_sizes[i]-1;
k += bucket_sizes[i];
}
return n;
}

int number_range_index(int number, int number_of_ranges, const struct range ranges[]) {
int i;
for(i=0; i<number_of_ranges; ++i)
if(number >= ranges[i].lo && number <= ranges[i].hi)
return i;
return number_of_ranges;
}

#define MAX_RANGES 50

int main(int argc, char *argv[]) {
int i;
struct range ranges[MAX_RANGES];

if(argc != 5) {
printf("usage: %s <min> <max> <number_of_ranges> <number>\n", argv);
return EXIT_FAILURE;
}

int min = atoi(argv);
int max = atoi(argv);
int number_of_ranges = atoi(argv);
int number = atoi(argv);

assert(max > min);
assert(number >= min && number <= max);
assert(number_of_ranges > 0);
assert(number_of_ranges <= MAX_RANGES);

printf("min=%d max=%d number_of_ranges=%d number=%d\n\n", min, max, number_of_ranges, number);

int n = generate_ranges(min, max, number_of_ranges, ranges);
for(i=0; i<number_of_ranges; i++) {
if(i<n)
printf("%s[%d-%d]", i>0?",":"", ranges[i].lo, ranges[i].hi);
else
printf("%s[]", i>0?",":"");
}
printf("\n\n");

int number_idx = number_range_index(number, n, ranges);
printf("method(%d)->[%d,%d]\n", number, ranges[number_idx].lo, ranges[number_idx].hi);

return EXIT_SUCCESS;
}
``````
• Is there any need to support multiple passes of surplus distribution? The modulo should never return a value greater than the divisor (which is the number of buckets). – Techrocket9 Jun 22 '17 at 21:51

Let `n` be the number of ranges. If you can divide your range into equal subranges, you can do it like this:

``````length_of_range = (max - min + 1) / n

For i = 1 to n:
start_of_range(i) = length_of_range * (i-1) + min
end_of_range(i) = start_of_range(i) + length_of_range - 1

method(number) = (number - min) / length_of_range + 1   // '/' is integer division
``````

If you can't divide them into equal subranges, the first `(max - min + 1) % n` subranges should have length `((max - min + 1) / n) + 1` and the rest should have length `(max - min + 1) / n`. Knowing that, you should be able to adjust the above formulas yourself.

• Thanks, but for min=1 and max=9 length_of_range would be 1 which is not correct. – tymtam Feb 21 '13 at 1:09
• You can't have min = 1 and max = 9 (and number of ranges = 5) if you want to divide your range into subranges of equal length. If that's not what you're looking for, you'll have to explain what is it that you're looking for more precisely. Until then, -1 for being too unclear (and not answering Standback's question). – iCanLearn Feb 21 '13 at 8:27
• I forgot to say that your code would also not work if the range would be [10-19] or any range that doesn't start at 0. – tymtam Feb 22 '13 at 5:40
• @Tymek: There's a very simple way to translate the [10-19] problem into a [0-9] problem: subtract 10 from the min and max. To get it back, just add 10 back. – Michael Shaw Feb 22 '13 at 20:40
• @MichaelShaw This was missing in the original answer and has been kindly adjusted. – tymtam Feb 25 '13 at 2:27

Here's a C++11 version of Oskar N's answer:

``````/** Divides a given range of values into consecutive sub-ranges as evenly as possible.
* Returns a vector of pairs.  The first member of each pair is the min and the second, the max.
*/
std::vector< std::pair<int, int> > generateSubRanges( int mainRangeMin,
int mainRangeMax,
int numberOfSubRanges )
{
std::vector<std::pair<int, int> > result;
std::vector<int> bucket_sizes;
int i;

//init vectors
bucket_sizes.reserve( numberOfSubRanges );
result.reserve( numberOfSubRanges );
for( i = 0; i < numberOfSubRanges; ++i ){
bucket_sizes.push_back( 0 );
result.push_back( {0, 0} );
}

int even_length = (mainRangeMax-mainRangeMin+1)/numberOfSubRanges;
for(i=0; i<numberOfSubRanges; ++i)
bucket_sizes[i] = even_length;

/* distribute surplus as evenly as possible across buckets */
int surplus = (mainRangeMax-mainRangeMin+1)%numberOfSubRanges;
for(i=0; surplus>0; --surplus, i=(i+1)%numberOfSubRanges)
bucket_sizes[i] += 1;

int n=0, k=mainRangeMin;
for(i=0; i<numberOfSubRanges && k<=mainRangeMax; ++i, ++n){
result[i] = { k, k+bucket_sizes[i]-1 };
k += bucket_sizes[i];
}

return result;
}
``````