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

Question

Простой вопрос - с учетом IList<T> как выполнить бинарный поиск без написания метода самостоятельно и без копирования данных в тип со встроенной поддержкой бинарного поиска. Мой текущий статус следующий.

• List<T>.BinarySearch() не является членом IList<T>
• Для List<T>
• IList<T> не наследуется от IList, поэтому использование ArrayList.Adapter() невозможно

Я склонен полагать, что это невозможно при использовании встроенных методов, но я не могу поверить, что такой базовый метод отсутствует в BCL / FCL.

Если это невозможно, кто может дать самую короткую, самую быструю, самую умную или самую красивую реализацию двоичного поиска для IList<T>?

UPDATE

Мы все знаем, что список должен быть отсортирован перед использованием бинарного поиска, поэтому вы можете предположить, что это так. Но я предполагаю (но не проверял), что та же проблема с сортировкой - как вы сортируете IList<T>?

ЗАКЛЮЧЕНИЕ

Кажется, что нет встроенного бинарного поиска для IList<T>. Для поиска и сортировки можно использовать методы First() и OrderBy() LINQ, но это также приведет к снижению производительности. Реализация его самостоятельно (как метод расширения) кажется лучшим, что вы можете сделать.

Answer 1

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

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

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

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

Answer 2

Я сомневаюсь, что в .NET есть такой метод бинарного поиска общего назначения, за исключением того, что он присутствует в некоторых базовых классах (но, по-видимому, не в интерфейсах), поэтому вот мой универсальный.

public static Int32 BinarySearchIndexOf<T>(this IList<T> list, T value, IComparer<T> comparer = null)
{
    if (list == null)
        throw new ArgumentNullException(nameof(list));

    comparer = comparer ?? Comparer<T>.Default;

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

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

    return ~lower;
}

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

Answer 3

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

Мне также нравится возвращать ~ ниже, когда совпадений не найдено. 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);
}

Answer 4

Я уже давно пытаюсь сделать это правильно. В частности, возвращаемые значения для крайних случаев, как указано в MSDN: http://msdn.microsoft.com/en-us/library/w4e7fxsh.aspx

Теперь я скопировал ArraySortHelper.InternalBinarySearch () из .NET 4.0 и сделал свой собственный аромат по разным причинам.

Использование:

var numbers = new List<int>() { ... };
var items = new List<FooInt>() { ... };

int result1 = numbers.BinarySearchIndexOf(5);
int result2 = items.BinarySearchIndexOfBy(foo => foo.bar, 5);

Это должно работать со всеми типами .NET. До сих пор я пробовал int, long и double.

Реализация:

public static class BinarySearchUtils
{
    public static int BinarySearchIndexOf<TItem>(this IList<TItem> list, TItem targetValue, IComparer<TItem> comparer = null)
    {
        Func<TItem, TItem, int> compareFunc = comparer != null ? comparer.Compare : (Func<TItem, TItem, int>) Comparer<TItem>.Default.Compare;
        int index = BinarySearchIndexOfBy(list, compareFunc, targetValue);
        return index;
    }

    public static int BinarySearchIndexOfBy<TItem, TValue>(this IList<TItem> list, Func<TItem, TValue, int> comparer, TValue value)
    {
        if (list == null)
            throw new ArgumentNullException("list");

        if (comparer == null)
            throw new ArgumentNullException("comparer");

        if (list.Count == 0)
            return -1;

        // Implementation below copied largely from .NET4 ArraySortHelper.InternalBinarySearch()
        int lo = 0;
        int hi = list.Count - 1;
        while (lo <= hi)
        {
            int i = lo + ((hi - lo) >> 1);
            int order = comparer(list[i], value);

            if (order == 0)
                return i;
            if (order < 0)
            {
                lo = i + 1;
            }
            else
            {
                hi = i - 1;
            }
        }

        return ~lo;
    }
}

Юнит-тесты:

[TestFixture]
public class BinarySearchUtilsTest
{
    [Test]
    public void BinarySearchReturnValueByMsdnSpecification()
    {
        var numbers = new List<int>() { 1, 3 };

        // Following the MSDN documentation for List<T>.BinarySearch:
        // http://msdn.microsoft.com/en-us/library/w4e7fxsh.aspx

        // The zero-based index of item in the sorted List(Of T), if item is found;
        int index = numbers.BinarySearchIndexOf(1);
        Assert.AreEqual(0, index);

        index = numbers.BinarySearchIndexOf(3);
        Assert.AreEqual(1, index);


        // otherwise, a negative number that is the bitwise complement of the index of the next element that is larger than item
        index = numbers.BinarySearchIndexOf(0);
        Assert.AreEqual(~0, index);

        index = numbers.BinarySearchIndexOf(2);
        Assert.AreEqual(~1, index);


        // or, if there is no larger element, the bitwise complement of Count.
        index = numbers.BinarySearchIndexOf(4);
        Assert.AreEqual(~numbers.Count, index);
    }
}

Я просто вычеркнул это из своего собственного кода, поэтому, пожалуйста, прокомментируйте, если он не работает из коробки.

Надеюсь, что это решит проблему с работающей реализацией раз и навсегда, по крайней мере, в соответствии со спецификациями MSDN.

Answer 5

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

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

Answer 6

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

Answer 7

Вы можете использовать List<T>.BinarySearch(T item). Если вы хотите использовать пользовательский компаратор, используйте List<T>.BinarySearch(T item, IComparer<T> comparer). Посмотрите эту ссылку MSDN для более подробной информации.

Answer 8

Если вам нужна готовая реализация для бинарного поиска на IList<T> s, В Power Collections Wintellect есть один (в 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>
{
    // ...
}

Answer 9

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

Answer 10

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

using System.Linq;

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

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