Search sorted List<Long> for closest and less than

Question

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.

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

Answer 1

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.

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

So, the code would look like:

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

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