便于查找的数据结构

Question

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

将数据集存储到某种数据结构中以便于查找
如果不存在完全匹配，则选择最接近的（A 值得到 B）
如果恰好介于两者之间，则选择 A 的较高值以获得 B

我有一对数字，例如 -

我只会知道 A 的值，应该通过应用上述规则进行直接查找来找出/导出 B 的值。

示例 - 1

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

示例 - 2

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

示例 - 3

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

有什么建议吗？

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

Answer 1

将 A 和 B 存储在 arrays/lists 中，按 A 中的值排序。

使用修改后的二分查找形式查找 A 的精确值或最接近值（满足条件 2 和 3）。

Answer 2

听起来像是家庭作业，所以我的答案将采用算法建议的形式。

将值对存储在二维数组中，按 "A" 的升序存储。要找到结果，请使用二进制搜索找到“A 的最接近低值”，如果不准确，请使用索引+1。

Answer 3

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

它有一些方法可以让你得到一个键的 'floor' 和 'ceiling'。之后，一点点数学会给你你真正想要的价值 return:

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;
}

注意：当没有 floor/ceiling 时，我没有费心去检查适当的 null，但你明白了。

便于查找的数据结构

Data Structure for easy look up

java

algorithm

lookup

java-6

data-structures