Cómo utilizar BinarySearch para la lista <T>

Question

Vamos a empezar con esta sobrecarga de la Lista BinarySearch:

public int BinarySearch(T item, IComparer<T> comparer); 

Es bien sabido que la lista debe ser ordenada con el IComparer apropiado antes de usar BinarySearch. Pero luego: para buscar en la lista, deberá proporcionar un elemento T. Esto es bastante inesperado cuando se utiliza para buscar elementos en la lista en función de las propiedades de estos elementos (es decir, utilizando Linq o delegados/predicados). ¡Porque cuando ya tengo mi artículo T no tengo que buscarlo!

Ahora estaba implementando el código C++ en C# y vi que el programador C++ usaba búsquedas binarias de estilo C++ en todas partes en su código de la siguiente manera. Primero hizo un nuevo artículo T y le dio a este artículo T las propiedades que estaba buscando. Luego buscó en la lista con ella, para encontrar el índice de un artículo en la lista con las mismas propiedades. El comparador de C++, por supuesto, se adaptó a estas propiedades.

Esta es una manera bastante diferente de buscar elementos en una lista. BinarySearch hace un artículo dummy T y busca un índice con el que puede recuperar el artículo real T en la lista. Desde el punto de vista de Linq, esto se siente antinatural.

Mis preguntas son:

¿Me dan una descripción correcta de la idea detrás de BinarySearch?

¿Crees que es posible usar una búsqueda de estilo Linq con BinarySearch sin hacer primero un ítem ficticio T?

Answer 1

Did I give a correct description of the idea behind BinarySearch?
Sí.

Do you think it is possible to use a Linq style search with BinarySearch without making a dummy T item first?
No está en la forma actual. Podrías usar una envoltura que crearía la T ficticia para ti, pero solo funcionaría para Ts específicos (con constructores sin parámetros, etc.).

Answer 2

En realidad, no hay nada similar en LINQ, pero puedes construir tus propias extensiones. Este ejemplo le permiten pasar no es un elemento ficticio, pero, por ejemplo, sólo la propiedad utilizada en el comparador el original:

public static int FindFirstIndexGreaterThanOrEqualTo<TElement, TKey>(
       this IList<TElement> keySortedCollection, 
       TKey key, 
       Func<TElement, TKey> keySelector, 
       IComparer<TKey> keyComparer) 
{ 
    int begin = 0; 
    int end = keySortedCollection.Count; 
    while (end > begin) 
    { 
     int index = (begin + end)/2; 
     TElement el = keySortedCollection[index]; 
     TKey currElKey = keySelector(el); 
     if (keyComparer.Compare(currElKey, key) >= 0) 
      end = index; 
     else 
      begin = index + 1; 
    } 
    return end; 
} 

public static int FindFirstIndexGreaterThanOrEqualTo<TElement, TKey>(
       this IList<TElement> keySortedCollection, 
       TKey key, 
       Func<TElement, TKey> keySelector) 
{ 
    return FindFirstIndexGreaterThanOrEqualTo(keySortedCollection, 
               key, 
               keySelector, 
               Comparer<TKey>.Default); 
} 

Con estos métodos, usted puede hacer una comparación que es un subconjunto de la misma que utilizó originalmente para ordenar la colección

Obviamente, cuando utiliza un subconjunto del comparador original, no puede estar seguro de encontrar un solo índice. Entonces estos métodos devuelven un límite inferior de búsqueda binaria.