java - 便于查找的数据结构

Question

我正在寻找 java 中的数据结构/算法来执行以下操作 -

1. 将数据集存储到某种数据结构中以便于查找
2. 如果不存在完全匹配，则选择最接近的(A 值得到 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]

有什么建议吗？

根据评论更新 -log(N) 查找是可以接受的。我愿意自己实现它，但需要有关如何实现它的建议。 A 的范围在 0 到 1000 之间变化，具有 1 位精度点。

Answer 1

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

它有一些方法可以让您获得 key 的“下限”和“上限”。之后，进行一些数学运算即可得到您实际想要返回的值:

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 检查，但你明白了。