Comment implémenter un algorithme de recherche binaire qui renvoie un itérateur en C ?

Algorithme de recherche binaire renvoyant un itérateur en C

En C, l'algorithme std::binary_search fournit un moyen pratique pour effectuer une recherche binaire sur les conteneurs triés. Cependant, il renvoie uniquement un booléen indiquant si l'élément existe, ce qui peut ne pas être suffisant pour certaines applications.

Exigence d'un algorithme de retour d'itérateur

Le besoin se fait sentir un algorithme de recherche binaire qui renvoie un itérateur pointant vers le résultat plutôt qu'un booléen. Cela permet aux développeurs d'accéder à l'élément réel trouvé ou de déterminer s'il n'est pas présent dans le conteneur.

Implémentation d'un algorithme de recherche binaire personnalisé

Puisqu'il n'existe pas de telle fonction disponible dans la bibliothèque standard, une implémentation personnalisée peut être créée à l'aide d'autres fonctions STL comme std::lower_bound, std::upper_bound ou std::equal_range .

Exemple d'implémentation

Voici une implémentation simple qui utilise std::lower_bound:

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

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

Alternativement, utiliser un std :: set

Une autre option consiste à utiliser un std :: set, qui conserve les éléments triés et fournit une méthode find (touche T) qui renvoie un itérateur à l'élément spécifié. . Cependant, cette approche peut ne pas convenir si plusieurs instances du même élément sont requises dans le conteneur.

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!