Collections - The Java Programming Language - page 888

Sorts list in ascending order, according to its elements' nat-
ural ordering.
public static <T> void sort(List<T> list, Comparator<? super T> comp)
Sorts list according to comp .
public static <T> int binarySearch(List<? extends Comparable<? super
T>> list,T key)
Uses a binary search algorithm to find a key object in the list ,
returning its index. The list must be in its elements' natural
order. If the object is not found, the index returned is a neg-
ative value encoding a safe insertion point.
public static <T> int binarySearch(List<? extends T> list, T key,
Comparator<? super T> comp)
Uses a binary search algorithm to find a key object in the list ,
returning its index. The list must be in the order defined by
comp . If the object is not found, the index returned is a negat-
ive value encoding a safe insertion point.
The phrase "a negative value encoding a safe insertion point" requires
some explanation. If you use a binarySearch method to search for a key
that is not found, you will always get a negative value. Specifically, if i is
the index at which the key could be inserted and maintain the order, the
value returned will be ( i +1). (The return value algorithm ensures that
the value will be negative when the key is not found, since zero is a val-
id index in a list.) So using the binarySearch methods you can maintain a
list in sorted order: Search the list to see if the key is already present.
If not, insert it according to the return value of binarySearch :
public static <T extends Comparable<? super T>>
void ensureKnown(List<T> known, T value)
{
int indexAt = Collections.binarySearch(known, value);