1

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?

Dave Newton
  • 158,873
  • 26
  • 254
  • 302
alisianoi
  • 2,003
  • 3
  • 31
  • 46

1 Answers1

2

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).

Dirk
  • 30,623
  • 8
  • 82
  • 102
  • 1
    can't really sort the list if the elements don't compare to each other:) – ZhongYu Oct 22 '16 at 18:42
  • @ZhongYu -- How you came up with the sorted list is of no concern to `binarySearch`. If you want to sort the list, you have to be able to compare the list items. But `binarySearch` only wants to search through the list, not sort its elements. That said: of course, binary search won't work, if the order, by which the list is sorted is not compatible to the one used when searching... – Dirk Oct 22 '16 at 18:49
  • Just speaking practically. But, even if we indulge a little in thought games, it is still necessary that the list elements compare to each other. This is because the element type, `V`, must be a subtype of `Comparable`, and `V` must be a subtype of `X`, therefore `V.compareTo(V)` is possible. See http://stackoverflow.com/a/34780320/2158288 . This is not apparent from the type system, but it must be true if the contracts of `Comparable` are properly implemented, therefore we can reasonably do runtime casts to compare elements with each other. – ZhongYu Oct 22 '16 at 19:23