THE Java™ Programming Language, Fourth Edition

Returns the index of the start of the first sublist of source that is equal to

target.

public static intlastIndexOfSubList(List<?> source, List<?>

target)

Returns the index of the start of the last sublist of source that is equal to

target.

There are also methods for sorting and searching lists:

public static <T extends Comparable<? super T>> void

sort(List<T> list)

Sorts list in ascending order, according to its elements' natural ordering.

public static <T> voidsort(List<T> list, Comparator<? super T>

comp)

Sorts list according to comp.

public static <T> intbinarySearch(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 negative value encoding a safe insertion point.

public static <T> intbinarySearch(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 negative 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 valid 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 known, T value)
{
int indexAt = Collections.binarySearch(known, value);
if (indexAt < 0) // not in the list -- insert it
known.add(-(indexAt + 1), value);
}

If the list of known elements does not include the given value, this method will insert the value in its place
in the list based on its natural ordering.