Как выполнить двоичный поиск на IList <T>?

Мне нравится решение с методом расширения. Тем не менее, уместно сделать небольшое предупреждение.

Фактически это реализация Джона Бентли из его книги «Жемчужины программирования», и она незначительно страдает от ошибки с числовым переполнением, которая оставалась незамеченной в течение 20 лет или около того. (Верхний + нижний) может переполнять Int32, если у вас есть большое количество элементов в IList. Решением этой проблемы является выполнение среднего вычисления немного по-другому, используя вместо этого вычитание; Средний = Нижний + (Верхний - Нижний) / 2;

Бентли также предупреждал в «Жемчужине программирования», что хотя алгоритм двоичного поиска был опубликован в 1946 году, а первая правильная реализация не была опубликована до 1962 года.

http: // en.wikipedia.org/wiki/Binary_search#Numerical_difficulty

У вас может возникнуть пара проблем с двоичным поиском IList . Во-первых, как вы упомянули, метод BinarySearch в List не является членом IList интерфейс. Во-вторых, у вас нет возможности отсортировать список перед поиском (что необходимо сделать для работы бинарного поиска).

Я думаю, что лучше всего создать новый List , отсортируйте его, а затем выполните поиск. Это не идеально, но у вас не так много вариантов, если у вас есть IList .

Если вы можете использовать .NET 3.5, вы можете использовать сборку в методах расширения Linq:

using System.Linq;

IList<string> ls = ...;
var orderedList = ls.OrderBy(x => x).ToList();
orderedList.BinarySearch(...);

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

Обратите внимание, что хотя List и IList не имеют метода BinarySearch, SortedList имеет.

Если вам нужна готовая реализация для двоичного поиска на IList s, в Wintellect Power Collections есть одна (в Algorithms.cs ):

/// <summary>
/// Searches a sorted list for an item via binary search. The list must be sorted
/// by the natural ordering of the type (it's implementation of IComparable&lt;T&gt;).
/// </summary>
/// <param name="list">The sorted list to search.</param>
/// <param name="item">The item to search for.</param>
/// <param name="index">Returns the first index at which the item can be found. If the return
/// value is zero, indicating that <paramref name="item"/> was not present in the list, then this
/// returns the index at which <paramref name="item"/> could be inserted to maintain the sorted
/// order of the list.</param>
/// <returns>The number of items equal to <paramref name="item"/> that appear in the list.</returns>
public static int BinarySearch<T>(IList<T> list, T item, out int index)
        where T: IComparable<T>
{
    // ...
}

Имейте в виду, что двоичный поиск может быть довольно неэффективным для некоторых реализаций списков. Например, для связанного списка это O (n), если вы реализуете его правильно, и O (n log n), если вы реализуете его наивно.

Вот моя версия кода Лассе. Я считаю полезной возможность использовать лямбда-выражение для выполнения поиска. При поиске в списке объектов оно позволяет передавать только ключ, который использовался для сортировки. Реализации, использующие IComparer, тривиально вытекают из этой.

Мне также нравится возвращать ~lower, когда не найдено ни одного совпадения. Array.BinarySearch делает это, и это позволяет вам знать, куда должен быть вставлен искомый элемент, чтобы сохранить упорядоченность.

/// <summary>
/// Performs a binary search on the specified collection.
/// </summary>
/// <typeparam name="TItem">The type of the item.</typeparam>
/// <typeparam name="TSearch">The type of the searched item.</typeparam>
/// <param name="list">The list to be searched.</param>
/// <param name="value">The value to search for.</param>
/// <param name="comparer">The comparer that is used to compare the value
/// with the list items.</param>
/// <returns></returns>
public static int BinarySearch<TItem, TSearch>(this IList<TItem> list,
    TSearch value, Func<TSearch, TItem, int> comparer)
{
    if (list == null)
    {
        throw new ArgumentNullException("list");
    }
    if (comparer == null)
    {
        throw new ArgumentNullException("comparer");
    }

    int lower = 0;
    int upper = list.Count - 1;

    while (lower <= upper)
    {
        int middle = lower + (upper - lower) / 2;
        int comparisonResult = comparer(value, list[middle]);
        if (comparisonResult < 0)
        {
            upper = middle - 1;
        }
        else if (comparisonResult > 0)
        {
            lower = middle + 1;
        }
        else
        {
            return middle;
        }
    }

    return ~lower;
}

/// <summary>
/// Performs a binary search on the specified collection.
/// </summary>
/// <typeparam name="TItem">The type of the item.</typeparam>
/// <param name="list">The list to be searched.</param>
/// <param name="value">The value to search for.</param>
/// <returns></returns>
public static int BinarySearch<TItem>(this IList<TItem> list, TItem value)
{
    return BinarySearch(list, value, Comparer<TItem>.Default);
}

/// <summary>
/// Performs a binary search on the specified collection.
/// </summary>
/// <typeparam name="TItem">The type of the item.</typeparam>
/// <param name="list">The list to be searched.</param>
/// <param name="value">The value to search for.</param>
/// <param name="comparer">The comparer that is used to compare the value
/// with the list items.</param>
/// <returns></returns>
public static int BinarySearch<TItem>(this IList<TItem> list, TItem value,
    IComparer<TItem> comparer)
{
    return list.BinarySearch(value, comparer.Compare);
}

Обратите внимание, что есть ошибка в реализации, предоставленной Антуаном ниже: при поиске элемента больше любого в списке. Возвращаемое значение должно быть ~ нижнее, а не ~ среднее. Декомпилируйте метод ArraySortHelper.InternalBinarySearch (mscorlib), чтобы увидеть реализацию фреймворка.