Besides sorting, the Collections
and Arrays
classes provide mechanisms to search a List
or array, as
well as to find the minimum and maximum values within a Collection
.
While you can use the contains()
method of List
to find if an element is part of the list, it assumes an unsorted
list. If you've previously sorted the List
, using Collections.sort()
,
then you can do a much quicker binary search using one of the two
overridden binarySearch()
methods. If the objects in the
List
implement Comparable
, then you don't need
to provide a Comparator
. Otherwise, you must provide a Comparator
.
In addition, if you sorted with a Comparator
, you must
use the same Comparator
when binary searching.
public static int binarySearch(List list, Object key)
public static int binarySearch(List list, Object key,
Comparator comparator)
If the List
to search subclasses the AbstractSequentialList
class (like LinkedList
), then a sequential search is
actually done.
Array searching works the same way. After using one of the Arrays.sort()
methods, you can take the resulting array and search for an
element. There are seven overridden varieties of binarySearch()
to search for a primitive (all but boolean
), and two to
search an Object
array, both with and without a Comparator
.
If the original List
or array is unsorted, the result
is non-deterministic.
Besides searching for specific elements within a List
,
you can search for extreme elements within any Collection
:
the minimum and maximum. If you know your collection is already
sorted, just get the first or last element. However, for unsorted
collections, you can use one of the min()
or max()
methods of Collections
. If the object in the collection
doesn't implement Comparable
, then you must provide a Comparator
.
Object max(Collection collection)
Object max(Collection collection, Comparator
comparator)
Object min(Collection collection)
Object min(Collection collection, Comparator
comparator)