java - 在列表中查找最近数字的最有效方法

Question

我知道他们怎么说预优化是万恶之源，但是我在这里更好奇什么是最有效的方法。知识库再多一点，你知道吗？

基本上我有一个整数集合，像这样:

final List<Integer> list = ImmutableList.of(1, 5, 10, 27, 57, 193);

现在我想找到最接近的数字，向下舍入。因此，例如我有数字 192。因此此列表的返回值将是“57”。如果数字是 58，同样适用。它只是找到下一个最小的数字。

目前我正在从末尾开始遍历列表，使用 for 然后返回列表的索引，这将是我想要的数字。我只是想知道是否有更有效的方法来做到这一点。

Answer 1

通用列表

如果对列表一无所知，遍历列表并记住当前最佳解决方案确实是最有效的。

但是，如果您计划进行数千次这样的查询，您可以先对列表进行排序。

排序列表

如果列表已排序，您可以使用 binarySearch(List<? extends Comparable<? super T>> list, T key) 方法。此方法返回新元素的插入点。如果该元素存在，则返回该元素的正索引。否则返回插入索引的按位求反。

然后你可以调用它:

//only to be used if list is sorted (a priori)
public int closestValue (List<Integer> list, int value) {
    int index = Collections.binarySearch(list,value);
    if(index < 0) {
        index = ~index-1;
    }
    return list.get(index);
}

jdoodle demo .

该方法将抛出 IndexOutOfBoundsException 如果没有这样的元素。

二进制搜索 可以在 O(log n) 中完成，但前提是 - 如前所述 - 如果列表已排序。