c# - カスタムタイプの二分探索配列

Question

オブジェクトの配列Aがあり、それぞれが0から1までのランダムなdoubleを持つパブリックフィールドValue（double）を持っています。Aはこのフィールドでソートされます。ダブルランダム=0.25を作成します。ここで、A [index] .Value>=randomを持つAから最初のオブジェクトを見つけたいと思います。何らかの方法でintindex= Array.BinarySearch（）を使用してこれを行うことはできますか？

Answer 1

BinarySearchこれは、使用できる実装です。通常受け入れられる他の引数に加えて、selector各項目について比較する必要がある実際のオブジェクトを決定する も受け入れます。また、値を見つけるために、配列の型ではなく、その型の値を受け入れます。 .

public static int BinarySearch<TSource, TKey>(this IList<TSource> collection
    , TKey item, Func<TSource, TKey> selector, Comparer<TKey> comparer = null)
{
    return BinarySearch(collection, item, selector, comparer, 0, collection.Count);
}
private static int BinarySearch<TSource, TKey>(this IList<TSource> collection
    , TKey item, Func<TSource, TKey> selector, Comparer<TKey> comparer
    , int startIndex, int endIndex)
{
    comparer = comparer ?? Comparer<TKey>.Default;

    while (true)
    {
        if (startIndex == endIndex)
        {
            return startIndex;
        }

        int testIndex = startIndex + ((endIndex - startIndex) / 2);
        int comparision = comparer.Compare(selector(collection[testIndex]), item);
        if (comparision > 0)
        {
            endIndex = testIndex;
        }
        else if (comparision == 0)
        {
            return testIndex;
        }
        else
        {
            startIndex = testIndex + 1;
        }
    }
}

使い方は簡単です:

public class Foo
{
    public double Value { get; set; }
}

private static void Main(string[] args)
{
    Foo[] array = new Foo[5];
    //populate array with values
    array.BinarySearch(.25, item => item.Value);
}

Answer 2

最善の方法は、自分でロールすることです。

public static class ListExtensions
{
        public static T BinarySearchFirst<T>(this IList<T> list, Func<T, int> predicate)
            where T : IComparable<T>
    {
        int min = 0;
        int max = list.Count;
        while (min < max)
        {
            int mid = (max + min) / 2;
            T midItem = list[mid];
            int comp = predicate(midItem);
            if (comp < 0)
            {
                min = mid + 1;
            }
            else if (comp > 0)
            {
                max = mid - 1;
            }
            else
            {
                return midItem;
            }
        }
        if (min == max &&
            predicate(list[min]) == 0)
        {
            return list[min];
        }
        throw new InvalidOperationException("Item not found");
    }
}

使用法：

var list = Enumerable.Range(1, 25).ToList();
var mid = list.Count / 2; //13

list.BinarySearchFirst(c => c >= 23 ? 0 : -1); // 23

コレクションの順序付け時に LINQ でバイナリ検索を使用できますか? に基づく