查找列表中最接近的数字的最有效方法

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。

二进制搜索可以Ô来完成（log n）的，但只是 - 就像之前说的 - 如果列表进行排序。

Answer 2

您可以对列表进行排序，然后使用类似二进制搜索的方法来查找最近的数字。

Answer 3

如果列表已排序，那么您可以在列表中执行二进制搜索，并且可以在Log（n）中获得您的否。

Answer 4

创建一个HashMap作为最大值的大小，然后用预期结果的密钥对填充地图。即map.put（6,5）; map.put（7,5）等等。

之后得到正确的值将在O（1）。

当然，创建地图需要更多的时间和资源，但是在无限的时间内这将产生最快的结果。