all3fox all3fox - 1 month ago 10
Java Question

How do these two generic signatures for Collections.binarySearch differ?

Here is the definition of

Collections.binarySearch
in Java:

static <T> int binarySearch(List<? extends Comparable<? super T> list, T key)
static <T> int binarySearch(List<? extends T> list, T key, Comparator<? super T> c)


How do they differ from the following definitions (which are similar to
Collections.sort
):

static <T extends Comparable<? super T>> int binarySearch(List<T> list, T key)
static <T> int binarySearch(List<T>, T x, Comparator<? super T>)


As I understand it:

The first definition allows you to search for a key of type T among the list of values, whose type is the same or "lower" of some type that knows how to compare either instances of type T or some "above" type.

The second definition allows you to search for a key of type T among a list of values, whose type is the same or "lower" than type T using a
Comparator
that knows how to compare either instances of type T or some "above" type.

Basically, what I do not understand is why aren't list contents enforced to have the same type as the key?

Answer

The first set of signatures is slightly more general. It works in odd edge-cases, which the second would reject. Consider the case of

 import java.sql.Timestamp;  // extends Date implements Comparable<Date> (!)
 import java.util.Date;

 List<Timestamp> timestamps = ...;
 Date key = ...;
 int index = Collections.binarySearch(timestamps, key);

This works for the first signature, but would be rejected as a type error under the second (you'd have to convert the key into a Timestamp first).

This may be a rare thing, but as the example of Timestamp and Date shows, there are examples of this in the JDK.

Maybe, it helps to remember, that binarySearch never needs to compare elements of the lists with other elements of the list. It only ever compares an element of the list with the given key, and thus, it makes sense, to require, that the list elements are comparable with the key (and not necessarily with each other).