Pouvez-vous implémenter un algorithme de recherche binaire efficace en C qui renvoie un itérateur au résultat de la recherche ?

Recherche d'un algorithme de recherche binaire efficace en C

Les programmeurs cherchent souvent à implémenter des algorithmes de recherche binaires efficaces qui offrent les avantages de la complexité temporelle logarithmique . Une exigence courante est que l'algorithme renvoie un itérateur pointant vers le résultat de la recherche plutôt qu'un simple booléen indiquant son existence.

La bibliothèque standard C fournit std::binary_search dans le fichier en-tête, mais il ne renvoie qu'un booléen. Comme l'a noté l'intervenant, cela peut être frustrant dans les situations où la vitesse d'une recherche binaire est souhaitée et où l'on sait que les données sont triées.

Heureusement, il existe des implémentations alternatives disponibles qui offrent la fonctionnalité souhaitée. Une option populaire consiste à utiliser un algorithme personnalisé qui exploite les fonctions std::lower_bound, std::upper_bound ou std::equal_range. Voici une version simplifiée d'une telle implémentation :

<code class="cpp">template<class Iter, class T>
Iter binary_find(Iter begin, Iter end, T val) {
    // Determine the lower bound using binary search
    Iter i = std::lower_bound(begin, end, val);

    // If the element is found, return the iterator to it
    if (i != end && !(val < *i)) {
        return i;
    }

    // Otherwise, return the end iterator
    else {
        return end;
    }
}</code>

Alternativement, un std::set peut être utilisé, qui garantit l'ordre des éléments et fournit la méthode find qui renvoie un itérateur vers l'élément souhaité. Cependant, il est important de considérer si les exigences sont compatibles avec l'utilisation d'un ensemble, en particulier dans les cas où plusieurs instances du même élément doivent être stockées.

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!