如何查找数字是否包含在java中的数字范围数组中

Question

我有一个java对象数组.

• 每个对象存储两个定义数字范围的长整数.
• 我已经保证对于范围内的所有对象,数字范围不重叠.

我想快速找到数组中的特定对象,给定一个可能(或可能不)属于对象定义的数字范围之一的数字.

我希望使用Array.binarySearch执行此操作,但这看起来不合适.

有关最佳方法的任何想法吗？

Answer 1

使用TreeMap.关键是两个长距离边界中较低的一个; 值是对象.

private TreeMap<Long, T> map = new TreeMap<Long, T>();

void insertObject(T object) {
    map.put(object, object.getLowerRangeBoundary());
}

T getObjectByKeyInRange(Long query) {
    // Get the first Object in the tree that corresponds with the query
    Map.Entry<Long, T> e = map.floorEntry(query);

    // If there's no entry, then the query value is lower than all ranges in the tree
    if (e == null) {
        return null;
    }

    T target = e.getValue();
    // "target" is the only object that can contain the query value
    // If the query value is within the range of "target", then it is our object
    if (query < target.getUpperRangeBoundary()) {
        return target;
    }

    // Nobody has the query value in their range; return null
    return null;
}