Как использовать BinarySearch для списка <T> - PullRequest
Новая
       27

Как использовать BinarySearch для списка <T>

10 голосов
/ 08 февраля 2011

Давайте начнем с перегрузки List BinarySearch: 

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

Хорошо известно, что список должен быть отсортирован с помощью соответствующего IComparer перед использованием BinarySearch.Но тогда: для поиска в списке вам нужно будет предоставить элемент T.Это довольно неожиданно, когда используется для поиска элементов в списке на основе свойств этих элементов (т. Е. С использованием Linq или делегатов / предикатов).Потому что, когда у меня уже есть мой T-элемент, мне не нужно его искать!

Теперь я реализовывал код C ++ в C # и увидел, что программист C ++ использует бинарный поиск в стиле C ++ везде в своем коде следующим образом.Сначала он сделал новый элемент T и дал этому элементу свойства, которые он искал.Затем он искал список с ним, чтобы найти индекс элемента в списке с такими же свойствами .Компаратор C ++, конечно, был адаптирован к этим свойствам.

Так что это совсем другой способ поиска элементов в Списке.BinarySearch создает элемент dummy T и ищет индекс, с помощью которого он может получить элемент real T в списке.С точки зрения Linq это кажется неестественным.

Мои вопросы:

Я правильно описал идею BinarySearch?

Считаете ли вы, что это возможно?использовать поиск в стиле Linq с BinarySearch без предварительного создания фиктивного элемента T?

Ответы [ 2 ]

5 голосов
/ 08 февраля 2011

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 (с конструкторами без параметров и т. Д.).

0 голосов
/ 08 февраля 2011

На самом деле, в 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);
}

С помощью этих методов вы можете дать сравнение, которое является подмножеством того, который вы изначальноиспользуется для сортировки коллекции.

Очевидно, что когда вы используете подмножество исходного компаратора, вы не можете быть уверены, что найдете один индекс.Таким образом, эти методы возвращают нижний предел бинарного поиска.

...