Recherche linéaire
La recherche linéaire vérifie chaque élément jusqu’au résultat ou à la fin.
Qu’est-ce que Recherche linéaire ?
La recherche linéaire vérifie chaque élément jusqu’au résultat ou à la fin.
Trouvez une cible dans des données non triées.
Points importants
- Testez les entrées vides, uniques, dupliquées et déjà triées.
- Séparez correction et optimisation.
- Préférez la bibliothèque standard en production.
Visualisation de Recherche linéaire
O(n)Utilisez Lecture ou Étape pour suivre chaque comparaison et déplacement de données.
Exemples de code C et C++
main.c
#include <stdio.h>
int find(const int *values, int size, int target) {
for (int index = 0; index < size; ++index) {
if (values[index] == target) return index;
}
return -1;
}
int main(void) {
int values[] = {14, 3, 27, 8, 19};
printf("index=%d\n", find(values, 5, 8));
}
index=3C++
main.cpp
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector values{14, 3, 27, 8, 19};
auto match = std::find(values.begin(), values.end(), 8);
std::cout << "index="
<< std::distance(values.begin(), match) << '\n';
}
index=3Comparaison entre C et C++
Les deux versions prennent O(n) au pire. C renvoie -1 comme indice absent ; C++ renvoie un itérateur comparé à end.
C
Boucles, pointeurs, tailles et buffers sont explicites.
C++
Itérateurs et algorithmes séparent opération et stockage.
Exercices pratiques
Exécutez les deux versions puis modifiez-les pour observer leurs garanties.
- Tracez chaque comparaison.
- Testez doublons et valeurs extrêmes.
- Comparez aux algorithmes standards.