c# - recursiva - busqueda secuencial en c++

¿Puede LINQ usar la búsqueda binaria cuando se ordena la colección?

Question

¿Puedo "instruir" a LINQ para que use la búsqueda binaria cuando se ordena la colección que estoy intentando buscar? Estoy usando un ObservableCollection<T> , rellenado con datos ordenados, y estoy tratando de usar Enumerable.First(<Predicate>) . En mi predicado, estoy filtrando por el valor del campo de mi colección ordenado por.

Answer 1

Bueno, puede escribir su propio método de extensión sobre ObservableCollection<T> , pero luego se usará para cualquier ObservableCollection<T> donde esté disponible su método de extensión, sin saber si está ordenado o no.

También tendrías que indicar en el predicado lo que querías encontrar, lo que se haría mejor con un árbol de expresiones ... pero eso sería un dolor para analizar. Básicamente, la firma de First no es realmente adecuada para una búsqueda binaria.

Le sugiero que no intente sobrecargar las firmas existentes , sino que escriba una nueva, por ejemplo

public static TElement BinarySearch<TElement, TKey>
    (this IList<TElement> collection, Func<TElement, TItem> keySelector,
     TKey key)

(No lo voy a implementar en este momento, pero puedo hacerlo más tarde si lo desea).

Al proporcionar una función, puede buscar por la propiedad por la que está ordenada la colección, en lugar de por los propios elementos.

Answer 2

La respuesta aceptada es muy buena.

Sin embargo, necesito que BinarySearch devuelva el índice del primer elemento que sea más grande, como lo hace la List<T>.BinarySearch() .

Así que observé su implementación usando ILSpy , luego la modifiqué para tener un parámetro selector. Espero que sea tan útil para alguien como para mí:

public static class ListExtensions
{
    public static int BinarySearch<T, U>(this IList<T> tf, U target, Func<T, U> selector)
    {
        var lo = 0;
        var hi = (int)tf.Count - 1;
        var comp = Comparer<U>.Default;

        while (lo <= hi)
        {
            var median = lo + (hi - lo >> 1);
            var num = comp.Compare(selector(tf[median]), target);
            if (num == 0)
                return median;
            if (num < 0)
                lo = median + 1;
            else
                hi = median - 1;
        }

        return ~lo;
    }
}

Answer 3

Que yo sepa, no es posible con los métodos incorporados. Sin embargo, sería relativamente fácil escribir un método de extensión que te permita escribir algo así:

var item = myCollection.BinarySearch(i => i.Id, 42);

(asumiendo, por supuesto, que la colección implementa IList; no hay forma de realizar una búsqueda binaria si no puede acceder a los elementos al azar)

Aquí hay una implementación de ejemplo:

public static T BinarySearch<T, TKey>(this IList<T> list, Func<T, TKey> keySelector, TKey key)
        where TKey : IComparable<TKey>
{
    if (list.Count == 0)
        throw new InvalidOperationException("Item not found");

    int min = 0;
    int max = list.Count;
    while (min < max)
    {
        int mid = min + ((max - min) / 2);
        T midItem = list[mid];
        TKey midKey = keySelector(midItem);
        int comp = midKey.CompareTo(key);
        if (comp < 0)
        {
            min = mid + 1;
        }
        else if (comp > 0)
        {
            max = mid - 1;
        }
        else
        {
            return midItem;
        }
    }
    if (min == max &&
        min < list.Count &&
        keySelector(list[min]).CompareTo(key) == 0)
    {
        return list[min];
    }
    throw new InvalidOperationException("Item not found");
}

(no probado ... algunos ajustes podrían ser necesarios) Ahora probado y arreglado;)

El hecho de que arroje una InvalidOperationException puede parecer extraño, pero eso es lo que Enumerable.First hace cuando no hay un elemento coincidente.

Answer 4

Tenga en cuenta que todos (? Al menos la mayoría) de los métodos de extensión utilizados por LINQ se implementan en IQueryable<T> o IEnumerable<T> o IOrderedEnumerable<T> o IOrderedQueryable<T> .

Ninguna de estas interfaces admite el acceso aleatorio y, por lo tanto, ninguna de ellas puede utilizarse para una búsqueda binaria. Uno de los beneficios de algo como LINQ es que puede trabajar con grandes conjuntos de datos sin tener que devolver todo el conjunto de datos de la base de datos. Obviamente, no puedes buscar algo en binario si aún no tienes todos los datos.

Pero como han dicho otros, no hay ninguna razón para que no pueda escribir este método de extensión para IList<T> u otros tipos de colección que admitan acceso aleatorio.

Answer 5

Enumerable.First(predicate) funciona en un IEnumarable<T> que solo admite enumeración, por lo tanto, no tiene acceso aleatorio a los elementos que contiene.

Además, su predicado contiene código arbitrario que eventualmente da como resultado verdadero o falso, por lo que no puede indicar si el elemento probado fue demasiado bajo o demasiado alto. Esta información sería necesaria para hacer una búsqueda binaria.

Enumerable.First(predicate) solo puede probar cada elemento en orden a medida que avanza en la enumeración.