Comment trouver l'index d'un élément avec la recherche binaire en C ?

Implémentation efficace de la recherche binaire en C

Trouver l'index ou l'itérateur d'un élément dans un conteneur trié est une opération fondamentale en C . Cependant, l'algorithme std::binary_search de la bibliothèque standard ne renvoie qu'un booléen indiquant l'existence de l'élément, pas sa position.

Considérons le cas où le conteneur est trié, et un algorithme de recherche binaire est préférable pour des raisons d'efficacité. . Une implémentation qui répond à ce besoin est requise.

Recherche binaire itérative personnalisée

Une approche consiste à implémenter un algorithme de recherche binaire itérative personnalisé. Voici un exemple d'implémentation :

<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 efficacement l'itérateur pointant vers l'élément recherché. Si la valeur trouvée ne correspond pas à val, elle renvoie l'itérateur end().

Solutions alternatives

Une autre option consiste à utiliser un std::set, qui garantit l'ordre des éléments et fournit une méthode find(T key) qui renvoie un itérateur à 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!