public class SortedLists
extends java.lang.Object
List
instances.
In this documentation, the terms greatest, greater, least, and
lesser are considered to refer to the comparator on the elements, and the terms
first and last are considered to refer to the elements' ordering in a
list.Modifier and Type | Class and Description |
---|---|
static class |
SortedLists.KeyAbsentBehavior
A specification for which index to return if the list contains no elements that compare as
equal to the key.
|
static class |
SortedLists.KeyPresentBehavior
A specification for which index to return if the list contains at least one element that
compares as equal to the key.
|
Modifier and Type | Method and Description |
---|---|
static <E> int |
binarySearch(java.util.List<? extends E> list,
E key,
java.util.Comparator<? super E> comparator,
SortedLists.KeyPresentBehavior presentBehavior,
SortedLists.KeyAbsentBehavior absentBehavior)
Searches the specified list for the specified object using the binary search algorithm.
|
static <E> int |
binarySearchAdd(java.util.List<? extends E> list,
E key,
java.util.Comparator<? super E> comparator)
Return the index of the first list element that compares as greater than the key, or
list.size() if there is no such element. |
static <E> int |
binarySearchGet(java.util.List<? extends E> list,
E key,
java.util.Comparator<? super E> comparator)
Return the index of the first list element that compares as equal to the key.
|
public static <E> int binarySearch(java.util.List<? extends E> list, E key, java.util.Comparator<? super E> comparator, SortedLists.KeyPresentBehavior presentBehavior, SortedLists.KeyAbsentBehavior absentBehavior)
Collections.sort(List, Comparator)
method), prior
to making this call. If it is not sorted, the results are undefined.
If there are elements in the list which compare as equal to the key, the choice of
SortedLists.KeyPresentBehavior
decides which index is returned. If no elements compare as equal to
the key, the choice of SortedLists.KeyAbsentBehavior
decides which index is returned.
This method runs in log(n) time on random-access lists, which offer near-constant-time access to each list element.
list
- the list to be searched.key
- the value to be searched for.comparator
- the comparator by which the list is ordered.presentBehavior
- the specification for what to do if at least one element of the list
compares as equal to the key.absentBehavior
- the specification for what to do if no elements of the list compare as
equal to the key.KeyPresentBehavior
, if the key is in the list;
otherwise the index determined by the KeyAbsentBehavior
.public static <E> int binarySearchAdd(java.util.List<? extends E> list, E key, java.util.Comparator<? super E> comparator)
list.size()
if there is no such element.public static <E> int binarySearchGet(java.util.List<? extends E> list, E key, java.util.Comparator<? super E> comparator)