Comment implémenter un algorithme de recherche binaire basé sur un itérateur pour les conteneurs C triés ?

Algorithme de recherche binaire avec retour d'itérateur pour les conteneurs C

L'algorithme std::binary_search de la STL identifie efficacement la présence d'un élément dans un élément trié conteneur, mais il ne renvoie qu'une valeur booléenne. Pour les scénarios où l'emplacement exact de l'élément est crucial, vous pouvez avoir besoin d'un algorithme de recherche basé sur un itérateur.

Pour répondre à ce besoin, l'algorithme de recherche binaire personnalisé suivant peut être utilisé :

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

Cet algorithme utilise std::lower_bound pour trouver le point d'insertion de la valeur dans le conteneur (si elle devait être insérée). Si la valeur est présente, l'itérateur est renvoyé ; sinon, l'itérateur de fin est renvoyé. Cette approche garantit à la fois vitesse et précision

Vous pouvez également envisager d'utiliser un std::set, qui fournit une fonction iterator find(T key) qui renvoie directement l'itérateur pointant vers l'élément donné. Cependant, cela peut ne pas convenir aux cas où des éléments en double sont requis.

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!