Comment effectuer une recherche binaire sur IList<T> ?

Question

Question simple - si l'on donne à un IList<T> comment effectuer une recherche binaire sans écrire la méthode soi-même et sans copier les données dans un type ayant un support de recherche binaire intégré. Ma situation actuelle est la suivante.

• List<T>.BinarySearch() n'est pas membre de IList<T>
• Il n'existe pas d'équivalent de la ArrayList.Adapter() méthode pour List<T>
• IList<T> n'hérite pas de IList , d'où l'utilisation de ArrayList.Adapter() n'est pas possible

J'ai tendance à croire que ce n'est pas possible avec les méthodes intégrées, mais je ne peux pas croire qu'une méthode aussi élémentaire soit absente de la BCL/FCL.

Si ce n'est pas possible, qui peut donner l'implémentation de recherche binaire la plus courte, la plus rapide, la plus intelligente ou la plus belle pour IList<T> ?

MISE À JOUR

Nous savons tous qu'une liste doit être triée avant d'utiliser la recherche binaire, vous pouvez donc supposer qu'elle l'est. Mais je suppose (sans l'avoir vérifié) que c'est le même problème avec le tri - comment trier ? IList<T> ?

CONCLUSION

Il semble qu'il n'y ait pas de recherche binaire intégrée pour les IList<T> . On peut utiliser First() y OrderBy() Les méthodes LINQ pour rechercher et trier, mais il est probable que les performances en pâtissent. L'implémenter soi-même (en tant que méthode d'extension) semble être la meilleure solution.

Answer 1

Je doute qu'il existe une méthode de recherche binaire d'usage général comme celle-ci dans .NET, à l'exception de celle présente dans certaines classes de base (mais apparemment pas dans les interfaces), alors voici ma méthode d'usage général.

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

Cela suppose bien sûr que la liste en question soit déjà triée, selon les mêmes règles que celles utilisées par le comparateur.

Answer 2

Voici ma version du code de Lasse. Je trouve utile de pouvoir utiliser une expression lambda pour effectuer la recherche. Lors d'une recherche dans une liste d'objets, il est possible de ne transmettre que la clé qui a été utilisée pour le tri. Les implémentations qui utilisent IComparer sont trivialement dérivées de celle-ci.

J'aime aussi renvoyer ~lower quand aucune correspondance n'est trouvée. Array.BinarySearch le fait et vous permet de savoir où l'élément recherché doit être inséré afin de conserver l'ordre.

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

J'aime la solution de la méthode d'extension. Toutefois, un petit avertissement s'impose.

Il s'agit en fait de l'implémentation de Jon Bentley dans son livre Programming Pearls et elle souffre modestement d'un bogue avec débordement numérique qui n'a pas été découvert pendant une vingtaine d'années. Le (upper+lower) peut dépasser Int32 si vous avez un grand nombre d'éléments dans la liste IL. Une solution à ce problème consiste à effectuer le calcul du milieu d'une manière un peu différente, en utilisant une soustraction à la place ; milieu = inférieur + (supérieur - inférieur) / 2 ;

Bentley a également averti dans Programming Pearls que l'algorithme de recherche binaire a été publié en 1946 et que la première implémentation correcte n'a été publiée qu'en 1962.

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

Answer 4

Vous allez rencontrer quelques problèmes lors de la recherche binaire d'une IList<T> Tout d'abord, comme vous l'avez mentionné, le BinarySearch sur la méthode List<T> n'est pas membre de la IList<T> l'interface. Deuxièmement, vous n'avez aucun moyen de trier la liste avant la recherche (ce que vous devez faire pour qu'une recherche binaire fonctionne).

Je pense que la meilleure solution consiste à créer un nouveau fichier List<T> , la trier, puis la rechercher. Ce n'est pas parfait, mais vous n'avez pas beaucoup d'options si vous avez une IList<T> .

Answer 5

Si vous avez besoin d'une implémentation prête à l'emploi pour la recherche binaire sur IList<T> s, Collections d'énergie de Wintellect a un (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>
{
    // ...
}