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

algorithms

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).

Best Answer

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[0]);
        return EXIT_FAILURE;
    }

    int min = atoi(argv[1]);
    int max = atoi(argv[2]);
    int number_of_ranges = atoi(argv[3]);
    int number = atoi(argv[4]);

    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;
}
Related Topic