リストBinarySearchのこのオーバーロードで始まるレッツ一覧<T>

Question

ためBinarySearchを使用する方法：

public int BinarySearch(T item, IComparer<T> comparer); 

よくリストはBinarySearchを使用する前に、appropiateたIComparerでソートする必要があることが知られています。しかし：リストを検索するには、Tアイテムを提供する必要があります。これは、これらの項目のプロパティに基づいて（つまり、Linqまたはデリゲート/述語を使用して）リスト内の項目を検索する場合には、むしろ予期しないことです。私のTアイテムをすでに持っているとき、私はそれを検索する必要はありません！

私はC＃でC++コードを実装していましたが、C++プログラマはC++スタイルのバイナリ検索をコード内のどこでも以下のように使用していました。最初に彼は新しいTアイテムを作って、このTアイテムに彼が探していたプロパティを与えました。次に彼はそれを使ってリストを検索し、という同じプロパティを持つリスト内のアイテムのインデックスであるを見つけました。もちろん、C++の比較者はこれらのプロパティに適合していました。

これは、リスト内の項目を参照するのとはかなり異なる方法です。 BinarySearchはダミー Tアイテムを作成し、リスト内の実際の Tアイテムを取り出すためのインデックスを検索します。 Linqの観点からは、これは不自然に感じる。

私の質問は以下のとおりです。

私はBinarySearch背後にあるアイデアの正しい説明を与えましたか？

ダミーのTアイテムを最初に作成せずに、BinarySearchでLinqスタイルの検索を使用することは可能でしょうか？

Answer 1

Did I give a correct description of the idea behind BinarySearch?
はい。

Do you think it is possible to use a Linq style search with BinarySearch without making a dummy T item first?
現在の形式ではありません。ダミーTを作成するラッパーを使用することもできますが、（パラメーターのないコンストラクターなどを使用して）特定のTsに対してのみ機能します。

Answer 2

実際、LINQには何も似ていませんが、独自の拡張機能を構築することはできます。 この例では、ダミーのアイテムを渡すことができませんが、元の比較演算に使用されるインスタンスのためだけのプロパティ：

public static int FindFirstIndexGreaterThanOrEqualTo<TElement, TKey>(
       this IList<TElement> keySortedCollection, 
       TKey key, 
       Func<TElement, TKey> keySelector, 
       IComparer<TKey> keyComparer) 
{ 
    int begin = 0; 
    int end = keySortedCollection.Count; 
    while (end > begin) 
    { 
     int index = (begin + end)/2; 
     TElement el = keySortedCollection[index]; 
     TKey currElKey = keySelector(el); 
     if (keyComparer.Compare(currElKey, key) >= 0) 
      end = index; 
     else 
      begin = index + 1; 
    } 
    return end; 
} 

public static int FindFirstIndexGreaterThanOrEqualTo<TElement, TKey>(
       this IList<TElement> keySortedCollection, 
       TKey key, 
       Func<TElement, TKey> keySelector) 
{ 
    return FindFirstIndexGreaterThanOrEqualTo(keySortedCollection, 
               key, 
               keySelector, 
               Comparer<TKey>.Default); 
} 

これらの方法では、あなたが最初に使用1のサブセットである比較を与えることができますコレクションをソートする。

明らかに、元の比較対象のサブセットを使用している場合、単一のインデックスを見つけることはできません。したがって、これらのメソッドはバイナリ検索の下限を返します。