int resultIndex(int higherIndex) {
return higherIndex;
}
},
/**
* Return {@code ~insertionIndex}, where {@code insertionIndex} is defined as the point at
* which the key would be inserted into the list: the index of the next higher element in the
* list, or {@code list.size()} if there is no such element.
*
* Note that the return value will be {@code >= 0} if and only if there is an element of the
* list that compares as equal to the key.
*
*
This is equivalent to the behavior of
* {@link java.util.Collections#binarySearch(List, Object)} when the key isn't present, since
* {@code ~insertionIndex} is equal to {@code -1 - insertionIndex}.
*/
INVERTED_INSERTION_INDEX {
@Override
public int resultIndex(int higherIndex) {
return ~higherIndex;
}
};
abstract int resultIndex(int higherIndex);
}
/**
* Searches the specified naturally ordered list for the specified object using the binary search
* algorithm.
*
* Equivalent to {@link #binarySearch(List, Function, Object, Comparator, KeyPresentBehavior,
* KeyAbsentBehavior)} using {@link Ordering#natural}.
*/
public static int binarySearch(List extends E> list, E e,
KeyPresentBehavior presentBehavior, KeyAbsentBehavior absentBehavior) {
checkNotNull(e);
return binarySearch(
list, checkNotNull(e), Ordering.natural(), presentBehavior, absentBehavior);
}
/**
* Binary searches the list for the specified key, using the specified key function.
*
* Equivalent to {@link #binarySearch(List, Function, Object, Comparator, KeyPresentBehavior,
* KeyAbsentBehavior)} using {@link Ordering#natural}.
*/
public static int binarySearch(List list,
Function super E, K> keyFunction, K key, KeyPresentBehavior presentBehavior,
KeyAbsentBehavior absentBehavior) {
return binarySearch(
list,
keyFunction,
key,
Ordering.natural(),
presentBehavior,
absentBehavior);
}
/**
* Binary searches the list for the specified key, using the specified key function.
*
* Equivalent to
* {@link #binarySearch(List, Object, Comparator, KeyPresentBehavior, KeyAbsentBehavior)} using
* {@link Lists#transform(List, Function) Lists.transform(list, keyFunction)}.
*/
public static int binarySearch(
List list,
Function super E, K> keyFunction,
K key,
Comparator super K> keyComparator,
KeyPresentBehavior presentBehavior,
KeyAbsentBehavior absentBehavior) {
return binarySearch(
Lists.transform(list, keyFunction), key, keyComparator, presentBehavior, absentBehavior);
}
/**
* Searches the specified list for the specified object using the binary search algorithm. The
* list must be sorted into ascending order according to the specified comparator (as by the
* {@link Collections#sort(List, Comparator) 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
* {@link KeyPresentBehavior} decides which index is returned. If no elements compare as equal to
* the key, the choice of {@link 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.
*
* @param list the list to be searched.
* @param key the value to be searched for.
* @param comparator the comparator by which the list is ordered.
* @param presentBehavior the specification for what to do if at least one element of the list
* compares as equal to the key.
* @param absentBehavior the specification for what to do if no elements of the list compare as
* equal to the key.
* @return the index determined by the {@code KeyPresentBehavior}, if the key is in the list;
* otherwise the index determined by the {@code KeyAbsentBehavior}.
*/
public static int binarySearch(List extends E> list, @Nullable E key,
Comparator super E> comparator, KeyPresentBehavior presentBehavior,
KeyAbsentBehavior absentBehavior) {
checkNotNull(comparator);
checkNotNull(list);
checkNotNull(presentBehavior);
checkNotNull(absentBehavior);
if (!(list instanceof RandomAccess)) {
list = Lists.newArrayList(list);
}
// TODO(user): benchmark when it's best to do a linear search
int lower = 0;
int upper = list.size() - 1;
while (lower <= upper) {
int middle = (lower + upper) >>> 1;
int c = comparator.compare(key, list.get(middle));
if (c < 0) {
upper = middle - 1;
} else if (c > 0) {
lower = middle + 1;
} else {
return lower + presentBehavior.resultIndex(
comparator, key, list.subList(lower, upper + 1), middle - lower);
}
}
return absentBehavior.resultIndex(lower);
}
}