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]。

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

这是一个线性时间算法。