コレクションが順序付けられている場合、LINQ はバイナリ検索を使用できますか? 質問する

私の知る限り、組み込みメソッドでは不可能です。ただし、次のようなコードを記述できる拡張メソッドを記述するのは比較的簡単です。

var item = myCollection.BinarySearch(i => i.Id, 42);

(もちろん、コレクションが IList を実装していることを前提としています。アイテムにランダムにアクセスできない場合は、バイナリ検索を実行する方法はありません)

実装例は次のとおりです:

public static T BinarySearch<T, TKey>(this IList<T> list, Func<T, TKey> keySelector, TKey key)
        where TKey : IComparable<TKey>
{
    if (list.Count == 0)
        throw new InvalidOperationException("Item not found");

    int min = 0;
    int max = list.Count;
    while (min < max)
    {
        int mid = min + ((max - min) / 2);
        T midItem = list[mid];
        TKey midKey = keySelector(midItem);
        int comp = midKey.CompareTo(key);
        if (comp < 0)
        {
            min = mid + 1;
        }
        else if (comp > 0)
        {
            max = mid - 1;
        }
        else
        {
            return midItem;
        }
    }
    if (min == max &&
        min < list.Count &&
        keySelector(list[min]).CompareTo(key) == 0)
    {
        return list[min];
    }
    throw new InvalidOperationException("Item not found");
}