java - 搜索最接近和小于的排序列表

Question

考虑一些 long称为 X和一个排序的 List<Long> .在 List<Long> 中查找索引或值的最有效算法是什么？即 (i) 小于 X , 和 (ii) 最接近 X在数轴上(假设条件 (i) 已满足)？

例如，这可能是一个问题设置:

long X = 500;
List<Long> foo = new Arraylist<Long>();
foo.add(450L);
foo.add(451L);    
foo.add(499L);
foo.add(501L);
foo.add(550L);

Collections.sort(foo); // It's always sorted.

我希望算法返回 499或返回与 499 关联的索引(在本例中为 i=2 )。

Answer 1

鉴于您列表中的值是唯一的，我建议您使用 Set ，更具体地说是 TreeSet ，因为您无论如何都会对列表进行排序。您可以使用 NavigableSet#floor(E) 完全符合您要求的方法。

Returns the greatest element in this set less than or equal to the given element, or null if there is no such element.

因此，代码如下所示:

long X = 500;
NavigableSet<Long> foo = new TreeSet<Long>();

foo.add(450L);
foo.add(451L);    
foo.add(499L);
foo.add(501L);
foo.add(550L);

System.out.println(foo.floor(X));   // 499

该方法也适用于用户定义的对象。只是你必须通过 Comparator<YourClass>到 TreeSet构造函数，同时实例化它。