搜索排序列表<长>对于最接近和小于 [英] Search sorted List&lt;Long&gt; for closest and less than

问题描述

考虑一些名为 X 的 long 和一个排序的 List.找到List中(i)小于X的索引或值的最有效算法是什么，并且(ii) 最接近数轴上的X(假设条件(i)已满足)?

Consider some long called X and a sorted List<Long>. What is the most efficient algorithm to find the index or value in the List<Long> that is (i) less than X, and (ii) The closest to X on the number line (assuming condition (i) has been satsified)?

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

For example this could be a problem setup:

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).

I would like the algorithm to either return 499 or to return the index associated with 499 (in this case i=2).

推荐答案

鉴于您列表中的值是唯一的，我建议您使用 Set，更具体地说是 TreeSet，反正你是整理你的清单.您可以使用 NavigableSet#floor(E) 方法完全符合您的要求.

Given that the values in your list are unique, I would suggest you to use a Set, more specifically a TreeSet, as you are anyways sorting your list. You can use the NavigableSet#floor(E) method which does exactly what you want.

返回这个集合中小于或等于给定元素的最大元素，如果没有这样的元素，则返回null.

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 传递给 TreeSet 构造函数.

The method would also work for user-defined objects. Just you have to pass a Comparator<YourClass> to the TreeSet constructor while instantiating it.

这篇关于搜索排序列表<长>对于最接近和小于的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！