Base de connaissancesCentre d’examen
FRFrançais
Choisir la langue13

CKTIS / C++

Recherche linéaire

La recherche linéaire examine les éléments successifs sans exiger que les données soient triées. En C++, std::find renvoie un itérateur vers la première correspondance ou l’itérateur de fin.

Version : C++23; repository compiler flag, production runtime not attested

Syntaxe

std::find(first, last, value)

La recherche linéaire (linear search) examine les éléments successifs jusqu’à trouver une correspondance ou jusqu’à épuisement de la plage. Les données n’ont pas besoin d’être triées.

Utilisez std::find(first, last, value) de <algorithm>. La plage [first, last) exclut last. Le résultat est un itérateur vers le premier élément pour lequel *it == value, et non un indice. En l’absence de correspondance, y compris dans une plage vide, le résultat est last ; ne le déréférencez jamais.

Pour n éléments, il faut au plus n comparaisons : le coût dans le pire des cas est O(n). L’exemple montre des doublons et une valeur absente. La soustraction d’itérateurs donne un indice commençant à zéro, car std::array fournit des itérateurs à accès aléatoire.

L’exemple vise C++23. La page citée est un projet de travail évolutif, et non une publication C++23 figée.

Exemples

#include <algorithm>
#include <array>
#include <iostream>

int main() {
    const std::array<int, 5> values{8, 3, 6, 3, 9};
    for (int target : {3, 7}) {
        const auto it = std::find(values.begin(), values.end(), target);
        std::cout << target << ": ";
        if (it != values.end()) {
            std::cout << "index " << (it - values.begin()) << '\n';
        } else {
            std::cout << "not found\n";
        }
    }
}

Résultat

3: index 1
7: not found

Le code affiché et le résultat déclaré ont été vérifiés dans un environnement isolé selon la méthode consignée dans la preuve de vérification de cette version exacte.

Sources