Search sorted List for closest and less than

问题:

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

回答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.

回答2:

/*Find the Closest Number in the list * @param list of Integers * @param num to the number find their closest * @return Closest number * */

public static int findClosestNumber(List list, int num) {
    if (list.size() > 0) { // Check list does not empty
        int smaller =
            (Integer)Collections.min(list); // get min number from the list
        int larger =
            (Integer)Collections.max(list); // get max number from the list

        for (int i = 0; i < list.size(); i++) { //Traverse list
            if (num == (Integer)list.get(i))   //if find the passed number in the list
                return num;                     //than return num
            if (num > (Integer)list.get(i) && smaller < (Integer)list.get(i)) // find nearest smaller
                smaller = (Integer)list.get(i);
            if (num < (Integer)list.get(i) && larger > (Integer)list.get(i)) // find nearest larger
                larger = (Integer)list.get(i);
        }
        return (num - smaller < larger - num ? smaller : larger); // return closest number
    }
return 0;
}

}

回答3:

You can use java's Collections.binarySearch for this, since your list is sorted.

In the spec, binary search returns:

the index of the search key, if it is contained in the list; otherwise, (-(insertion point) - 1). The insertion point is defined as the point at which the key would be inserted into the list: the index of the first element greater than the key, or list.size() if all elements in the list are less than the specified key. Note that this guarantees that the return value will be >= 0 if and only if the key is found.

First off, if you binary search and the element is in the list, you'll get a positive value (the index of the element), and can just return that (or if you still want an element that's less you can just walk backwards from there until you find one).

Otherwise, if you search for something that isn't in the list you can work backward from the return value to the index you want. If you search for 500 in your example list, the algorithm would return (-3 - 1) = -4. Thus, you can add 1 to get back to the insertion point (-3), and then multiply by -1 and subtract 1 to get the index BEFORE the first element GREATER than the one you searched for, which will either be an index that meets your 2 criteria OR -1 if all elements in the list are greater than the one you searched for.

The advantage of using binary search over a tree set is that it will likely have less overhead.