Comment implémenter un algorithme de recherche binaire en C qui renvoie l'emplacement de l'élément ?

Obtention d'un algorithme de recherche binaire C "utile"

Le C STL fournit un algorithme de recherche binaire, mais il renvoie uniquement un booléen indiquant si le l'élément existe. Pour les cas où l'emplacement exact de l'élément est requis, un algorithme plus complet est nécessaire.

Une option consiste à créer une fonction de recherche binaire personnalisée. Voici une implémentation simple :

<code class="cpp">template<class Iter, class T>
Iter binary_find(Iter begin, Iter end, T val) {
    // Find the lower bound in at most log(last - first) + 1 comparisons
    Iter i = std::lower_bound(begin, end, val);

    if (i != end && !(val < *i))
        return i; // found
    else
        return end; // not found
}</code>

Une autre approche consiste à utiliser un std::set, qui ordonne automatiquement les éléments et fournit une méthode find(T key) qui renvoie un itérateur à l'élément. Cependant, cela peut ne pas convenir si les données peuvent contenir des valeurs en double.

Pour les situations où la vitesse est critique, il est important de profiter des avantages d'une recherche binaire. Les algorithmes Lower_bound et upper_bound peuvent être inadéquats lorsque l'élément n'existe pas, car ils peuvent ne pas renvoyer l'itérateur de fin. La fonction binaire_find fournie ci-dessus résout ce problème et garantit le comportement correct.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!