algorithm - 如何确定一个范围内的数字？

Question

给定范围如 0..5.....20....25..40...50......100，我必须确定一个数字在哪个范围内。所以问题是确定数字在哪个范围内的最快方法，例如 aNum = 56 在 50....100 范围内。确定范围后，我将范围的起始编号分配给 aNum，在本例中为 50。所以最后，aNum = 50。

我只是想知道它是否可以花费恒定的时间 O(1) 。

任何建议将不胜感激。您可以使用任何数据结构来执行此操作。

Answer 1

对于显示的范围类型（​​可被 5 整除），以下算法很好：

1. 将所有范围划分为 5（因此，例如 25-40 实际上是 3 个范围：25-29、30-34 和 35-39。

2. 制作一个查找数组，将分段键为范围。因此，例如，如果范围 25-39 是 #4，段 25-29 是 #15，则 30-34 是 #16，而 35-39 是 #17。然后lookup[15] = 4，lookup[16]=4，lookup[17]=4，等等。

3. 现在是分工问题。将数字除以 5 得到 D，然后范围 # = lookup[D]。

如果您的范围是不规则的并且不能被一个公共数字整除，那么可以以内存为代价创建一个包含所有可能值的查找表。

这是一个线性时间算法。

Answer 2

假设存在N有序范围，则可以O(Log N)使用二进制搜索算法找到目标范围。少于那将是不可能的。例如，您可以考虑所有范围都相等的情况，例如：

1..2..3..4.. .. 99..100

在这种情况下，查找目标范围相当于在已排序的数组中查找数字，而在O(1).

Answer 3

这是一个示例算法：

1. 确定范围的数量以及每个范围的最小值和最大值。
2. 遍历所有范围并将数字与每个范围的最小值和最大值进行比较。
3. 如果它在任何范围内，请将其设置为等于该范围的最小值。
4. 如果它不在任何范围内，请执行所需的任何操作。

以下代码说明了在 C 中实现此算法的示例：

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

/*We assume there is a fixed number of ranges*/
#define RANGE_COUNT 4

int main(int argc, char** argv){
   /*Set the minimum and maximum values for each range*/
   int ranges[RANGE_COUNT][2] = {{0, 5}, {20, 20}, {25, 40}, {50, 100}};
   int x = 0, num = 0;

   /*In this example, we are using the command-line for input*/
   if(argc != 2){
      fprintf(stderr, "Usage: %s <number>", argv[0]);
      exit(1);
   }

   /*We need to ensure that the input is a number*/
   if(!(num = atoi(argv[1])) && argv[1][0] != '0'){
      fprintf(stderr, "Error: \"%s\" is not a number", argv[1]);
      exit(1);
   }

   /*See if the number is in any of the ranges*/
   for(x = 0; x < RANGE_COUNT; x++){
      if(num >= ranges[x][0] && num <= ranges[x][1]){
         /*If the number is in a range, say which one it is*/
         printf("The number %d is in the range %d..%d\n",
            num, ranges[x][0], ranges[x][1]);

         /*Set the number equal to the minimum value of the range it is in*/
         num = ranges[x][0];
         printf("num = %d\n", num);
         exit(0);
      }
   }

   /*If the number is not in any of these ranges, indicate that it is not*/
   printf("The number %d is not in any of these ranges\n", num);

   return 0;
}