使用java映射进行范围搜索

Question

我有一个用例，如果一个数字在0-10之间，它应该返回0，如果它在11-20之间，它应该返回1，以此类推

0 => 0-3, (0 and 3 are inclusive)
1 => 4-15, (4 and 15 are inclusive)
2 => 16-40, (16 and 40 are inclusive)
3 => 41-88, (41 and 88 are inclusive)
5 => 89-300 (89 and 300 are inclusive)

我在考虑如何实现java映射，但它不允许范围搜索

我对这样的东西感兴趣，我有一个函数

int foo() {

}

如果foo返回5，因为它位于0到10之间，所以我将使用0，如果foo返回25，则使用2

有什么想法吗

编辑：实际上，范围没有0-10、11-20那么简单。我希望能够进行范围搜索。很抱歉搞混了。根据我添加的正确示例的查询，数字是连续的

Answer 1

我认为你想要的是类似于foo()/10的东西，但这会让你的范围稍微偏离你所要求的范围。如果“地图”中的每个项目不遵循简单的模式，您总是可以对它们的两个端点进行比较

Answer 2

我可以想出一些可能的解决方案，解决范围不一致且存在“漏洞”的更一般问题。最简单的是：

1. 只需为所有有效键值填充一个映射，多个键映射到同一个值。假设您使用HashMaps，这应该是时间效率最高的（O（1）查找），尽管您在设置时有更多的工作，并且使用了更多的空间
2. 使用NavigableMap并使用floorEntry(key)进行查找。这应该是更少的时间效率（O（log（N）查找），但更节省空间

这里有一个使用NavigableMap的解决方案，允许在映射中出现“洞”

private static class Range {
   public int upper, value;
   ...
}

NavigableMap<Integer, Range> map = new TreeMap<Integer, Range>();
map.put(0, new Range(3, 0));       // 0..3     => 0
map.put(5, new Range(10, 1));      // 5..10    => 1
map.put(100, new Range(200, 2));   // 100..200 => 2

// To do a lookup for some value in 'key'
Map.Entry<Integer,Range> entry = map.floorEntry(key);
if (entry == null) {
    // too small
} else if (key <= entry.getValue().upper) {
    return entry.getValue().value;
} else {
    // too large or in a hole
}

另一方面，如果没有“孔”，则解决方案更简单：

NavigableMap<Integer, Integer> map = new TreeMap<Integer, Integer>();
map.put(0, 0);    // 0..4     => 0
map.put(5, 1);    // 5..10    => 1
map.put(11, 2);   // 11..200  => 2

// To do a lookup for some value in 'key'
if (key < 0 || key > 200) {
    // out of range
} else {
   return map.floorEntry(key).getValue();
}

Answer 3

在更一般的情况下，不能用算术来解决，您可以创建一个带有适当比较器的树形图。为边界值添加映射，然后使用ceilingEntry或floorEntry查找适当的匹配项

Answer 4

基于John Kugelman's answer，我需要类似的东西来进行日期范围搜索，该搜索包含与日期范围相关联的数据。。。下面是我如何应用它的一个示例。“日期”将是您的键，“范围数据”将是关联的数据

  long[] dates = new long[] {
    Instant.parse("1900-01-01T00:00:00Z").toEpochMilli(),
    Instant.parse("1950-01-01T00:00:00Z").toEpochMilli(),
    Instant.parse("1960-01-01T00:00:00Z").toEpochMilli(),
    Instant.parse("1970-01-01T00:00:00Z").toEpochMilli(),
    Instant.parse("1980-01-01T00:00:00Z").toEpochMilli(),
    Instant.parse("1990-01-01T00:00:00Z").toEpochMilli(),
    Instant.parse("2000-01-01T00:00:00Z").toEpochMilli(),
    Instant.parse("2010-01-01T00:00:00Z").toEpochMilli()
  };
  String[] rangeData = new String[] {
    "Before 1900 data", "Before 1950 data", "Before 1960 data", 
    "Before 1970 data", "Before 1980 data", "Before 1990 data", 
    "Before 2000 data", "Before 2010 data"
  };
  
  long searchDate = Instant.parse("1949-02-15T00:00:00Z").toEpochMilli();
  int result = Arrays.binarySearch(dates, searchDate);
  
  System.out.println("Result: " + result); 
  if (result == dates.length) {
      System.out.println("Date is after all ranges");
      System.out.println("Data: none");
  }
  else if (result >= 0) {
      System.out.println("Date is an exact match of " + Instant.ofEpochMilli(dates[result]));
      System.out.println("Data: " + rangeData[result]);
  }
  else {
      int resultIndex = Math.abs(result) - 1;
      System.out.println("Date is before idx: "+ resultIndex + " date " + Instant.ofEpochMilli(dates[resultIndex]));
      System.out.println("Data: " + rangeData[resultIndex]);
  }

结果

Result: -2
Date is before idx: 1 date 1950-01-01T00:00:00Z
Data: Before 1950 data

Answer 5

我认为最简单的解决方案是将范围上限的映射添加到范围映射到的值，然后继续增加数字（映射中的键），直到达到映射（即数字所在范围的上限）

另一种方法是使用范围内的所有条目填充映射，并为每个条目添加映射

哪一个更有效取决于您可能需要重复请求某个范围内的所有数字（使用后一种解决方案），还是只请求其中一些数字几次（使用第一种）

Answer 6

伪代码：

1. 将范围边界存储在平面数组中：new int[] {0, 3, 5, 15, 100, 300}
2. 在数组中进行二进制搜索，就像在数组中插入数字一样。见^{}
3. 如果插入点为偶数，则该数字不适合任何范围
4. 如果插入点为奇数，则它适合于相应的范围。例如，上述数组中10的插入点将是3，将其置于5和15之间，因此它属于第二个范围