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

StackOverflow https://stackoverflow.com/questions/967047

Вопрос

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

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

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

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

ОБНОВЛЯТЬ

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

ЗАКЛЮЧЕНИЕ

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

Это было полезно?

Решение

Я сомневаюсь, что в .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;
}

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

Другие советы

Мне нравится решение с методом расширения.Однако следует немного предупредить.

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

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

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

Вот моя версия кода Лассе.Я считаю полезным иметь возможность использовать лямбда-выражение для выполнения поиска.При поиске в списке объектов разрешается передать только тот ключ, который использовался для сортировки.Реализации, использующие 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);
}

Я уже некоторое время пытаюсь сделать это правильно.В частности, возвращаемые значения для крайних случаев, как указано в 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.

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

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

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

Если вам нужна готовая реализация бинарного поиска по IList<T>с, Коллекции мощности 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>
{
    // ...
}

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

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

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

using System.Linq;

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

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

Обратите внимание: хотя у List и IList нет метода BinarySearch, у SortedList он есть.

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top