はここで `Collections.binarySearch`署名

Question

を使用してバイナリ検索を実装することは従わなければならないバイナリ検索を実装する時、私の試みです：

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) 

しかし、私は、コードの重複を避けたいと実装の1つに委任うもう1つ（現在、最初から2番目）。

Non-static method cannot be referenced from a static context

方法：エラーで失敗し、

public class BinarySearch { 
    public static <Q extends Comparable<? super T>, T> 
    int search(List<Q> xs, T x) { 
     return search(xs, x, Q::compareTo); 
    } 

    public static <T> 
    int search(List<? extends T> xs, T x, Comparator<? super T> cmp) { 
     int l = 0, r = xs.size() - 1; 

     while (l <= r) { 
      int mid = l + (r - l)/2; 

      if (cmp.compare(xs.get(mid), x) == 0) 
       return mid; 

      if (cmp.compare(xs.get(mid), x) < 0) 
       r = mid - 1; 
      else 
       l = mid + 1; 
     } 

     return xs.size(); 
    } 
} 

残念ながら、これはコンパイルされません：私は、ワイルドカード?を取り除くために必要があるので、同様に第二ジェネリック型を使用することを行うために、私はそれを修正できますか？

PS：Collectionsからの署名は彼らのやり方を見て、なぜあなたは不思議に思うならば、ここでの説明は次のとおりです。How do these two generic signatures for Collections.binarySearch differ?

PPS：あなたはT::compareToを渡すことはできません（今削除された）の答えがあるように使用Comparatorが期待されるところにある。 Qを使用する理由https://github.com/all3fox/algos-java/blob/481f2c71952bf2c7510cb93cc1af8e90016ccf3b/src/main/java/io/github/all3fox/sort/QuickSort.java

Answer 1

実は、私は理解していない：

public static <T extends Comparable<T>> 
int search(List<? extends T> xs, T x) { 
    return search(xs, x, T::compareTo); 
} 

は、コンパイルして、私には十分に見えるだろうまあ、私はあなたが、ここではまさにそのクイックソートの私の作業実装であることができると信じて。 それは私の両方を行うことができます：

int search(List<? extends T> xs, final T x) { 
    return search(xs, x, new Comparator<T>() { 
     @Override 
     public int compare(T o1, T o2) { 
     return x.compareTo(o2); 
     } 
    }); 
} 

今ははっきりと見ることができます：xは型である必要があり、ここで

BinarySearch.search(new ArrayList<Timestamp>(), new Date()); 
BinarySearch.search(new ArrayList<Date>(), new Timestamp(0L)); 

非常に重要な点は、この実際の手段（多かれ少なかれ）ということです匹敵します。これはあなたのアプローチでは述べられていませんでした。代わりにタイプQが定義されていましたが、実際にはこのタイプの参加者はいませんでした。したがって、Comparatorは厳密には互換性がありませんでしたが、xのcompareToメソッドはコンパレータの実装であるためです。 BTWのもう1つのアプローチは、トリックにComparator.naturalOrder()を使用することですが、それでもTはComparableとして定義する必要があります。