.net - recursiva - ¿Cómo realizar una búsqueda binaria en IList<T>?

busqueda secuencial en c++

Question

Pregunta simple: dado un IList<T> ¿cómo se realiza una búsqueda binaria sin escribir el método usted mismo y sin copiar los datos a un tipo con soporte de búsqueda binario incorporado. Mi estado actual es el siguiente.

• List<T>.BinarySearch() no es miembro de IList<T>
• No hay un equivalente del método ArrayList.Adapter() para List<T>
• IList<T> no hereda de IList , por lo tanto, no es posible usar ArrayList.Adapter()

Tiendo a creer que no es posible con los métodos integrados, pero no puedo creer que ese método básico no se encuentre en BCL / FCL.

Si no es posible, ¿quién puede dar la implementación de búsqueda binaria más corta, más rápida, más inteligente o más hermosa para IList<T> ?

ACTUALIZAR

Todos sabemos que una lista debe ser ordenada antes de usar la búsqueda binaria, por lo tanto, puede suponer que sí lo es. Pero supongo (pero no lo verifiqué) que es el mismo problema con el género: ¿cómo clasifica IList<T> ?

CONCLUSIÓN

Parece que no hay una búsqueda binaria IList<T> para IList<T> . Uno puede usar los métodos First() y OrderBy() LINQ para buscar y ordenar, pero seguramente tendrá un golpe de rendimiento. Implementarlo usted mismo (como un método de extensión) parece lo mejor que puede hacer.

Answer 1

Aquí está mi versión del código de Lasse. Me parece útil poder usar una expresión lambda para realizar la búsqueda. Al buscar en una lista de objetos, solo permite pasar la clave que se usó para ordenar. Las implementaciones que usan IComparer se derivan trivialmente de esta.

También me gusta regresar ~ menor cuando no se encuentra una coincidencia. Array.BinarySearch lo hace y le permite saber dónde debe insertarse el elemento que ha buscado para poder realizar el pedido.

/// <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 2

Dudo que haya un método de búsqueda binaria de propósito general en .NET como ese, excepto el que está presente en algunas clases base (pero aparentemente no en las interfaces), así que aquí está mi propósito general.

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;
}

Por supuesto, esto supone que la lista en cuestión ya está ordenada, de acuerdo con las mismas reglas que usará el comparador.

Answer 3

He estado luchando para hacer esto bien desde hace un tiempo. En particular, los valores de retorno para casos extremos tal como se especifica en MSDN: msdn.microsoft.com/en-us/library/w4e7fxsh.aspx

Ahora copié el ArraySortHelper.InternalBinarySearch () de .NET 4.0 e hice mi propio sabor por varias razones.

Uso:

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

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

Esto debería funcionar con todos los tipos .NET. Intenté int, long y double hasta ahora.

Implementación:

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;
    }
}

Pruebas unitarias:

[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);
    }
}

Acabo de sacar esto de mi propio código, así que comente si no funciona de la caja.

Espero que esto solucione el problema con una implementación que funcione de una vez por todas, al menos según las especificaciones de MSDN.

Answer 4

Me gusta la solución con el método de extensión. Sin embargo, un poco de advertencia está en orden.

Esta es efectivamente la implementación de Jon Bentley de su libro Programming Pearls y sufre modestamente de un error con desbordamiento numérico que no se descubrió durante 20 años más o menos. El (superior + inferior) puede desbordar Int32 si tiene una gran cantidad de elementos en el IList. Una solución a esto es hacer el cálculo del medio de una manera un poco diferente usando una resta; Medio = Inferior + (Superior - Inferior) / 2;

Bentley también advirtió en Programming Pearls que mientras el algoritmo de búsqueda binaria se publicó en 1946 y la primera implementación correcta no se publicó hasta 1962.

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

Answer 5

Puede usar List<T>.BinarySearch(T item) . Si desea utilizar un comparador personalizado, utilice List<T>.BinarySearch(T item, IComparer<T> comparer) . Eche un vistazo a este link MSDN para más detalles.

Answer 6

Si necesita una implementación lista para la búsqueda binaria en IList<T> s, las Colecciones de energía de Wintellect tienen una (en 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 7

Si puede usar .NET 3.5, puede usar la compilación en los métodos de extensión Linq:

using System.Linq;

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

Sin embargo, esta es solo una forma ligeramente diferente de abordar la solución de Andrew Hare, y solo es realmente útil si buscas varias veces fuera de la misma lista ordenada.

Answer 8

Tenga en cuenta que hay un error en la implementación proporcionada por Antoine a continuación: cuando busca un elemento más grande que cualquiera en la lista. El valor de retorno debe ser ~ menor que ~ medio. Descompile el método ArraySortHelper.InternalBinarySearch (mscorlib) para ver la implementación del marco.

Answer 9

Tenga en cuenta que la búsqueda binaria puede ser bastante ineficiente para algunas implementaciones de listas. Por ejemplo, para una lista vinculada, es O (n) si la implementa correctamente, y O (n log n) si la implementa ingenuamente.

Answer 10

Tenga en cuenta que mientras List e IList no tienen un método BinarySearch, SortedList sí lo tiene.

Answer 11

Vas a tener un par de problemas al buscar binarios en un IList<T> . Primero, como mencionaste, el método BinarySearch en la List<T> no es miembro de la interfaz IList<T> . En segundo lugar, no tiene forma de ordenar la lista antes de buscarla (lo cual debe hacer para que funcione una búsqueda binaria).

Creo que tu mejor opción es crear una nueva List<T> , ordenarla y luego buscar. No es perfecto, pero no tienes muchas opciones si tienes un IList<T> .