数据结构,便于查找

Question

我在java中寻找一个数据结构/算法,它执行以下操作 -

1. 将数据集存储到某个数据结构中以便于查找
2. 如果不存在完全匹配,请选择最接近的值(获取B的值)
3. 如果恰好介于两者之间,请选择较高的A值来获得B.

我有一对数字,例如 -

A   B
80  0
76  1
64  3
56  4
48  10

我只知道A的值,并且应该通过应用上述规则进行直接查找来找出/得出B的值.

例子 - 1

如果我得到80的值,则输出为0

示例 - 2

如果我得到75的值,则输出为1 [根据规则2]

示例 - 3

如果我得到70的值,则输出为1 [根据规则3]

有什么建议？

基于注释的更新 - 日志(N)查找是可以接受的.我愿意自己实施它,但需要有关如何实现它的建议.A的范围在0到1000之间变化,具有1位精度点.

Answer 1

实际上已经有一个数据结构可以完全满足您的需求,这就是TreeMap.

它有一些方法可以让你获得一把钥匙的"地板"和"天花板".在那之后,一点点数学将获得您实际想要返回的价值:

public static TreeMap<Integer, Integer> tm = new TreeMap<>();

public static void main(String[] args) throws Exception {
    tm.put(80, 0);
    tm.put(76, 1);
    tm.put(64, 3);
    tm.put(56, 4);
    tm.put(48, 10);

    System.out.println(myGet(80));  // 0
    System.out.println(myGet(75));  // 1
    System.out.println(myGet(70));  // 1
}

public static int myGet(int key) {
    Integer value = tm.get(key);

    if (value == null) {
        Entry<Integer, Integer> floor = tm.floorEntry(key);
        Entry<Integer, Integer> ceiling = tm.ceilingEntry(key);

        if ((key - floor.getKey()) < (ceiling.getKey() - key)) {
            value = floor.getValue();
        } else {
            value = ceiling.getValue();
        }
    }

    return value;
}

注意:null当没有地板/天花板时,我没有正确检查,但你明白了.