Recherche séquentielle
Pour les articles homonymes, voir Recherche linéaire.
La recherche séquentielle ou recherche linéaire est un algorithme pour trouver une valeur dans une liste. Elle consiste simplement à considérer les éléments de la liste les uns après les autres, jusqu'à ce que l'élément soit trouvé, ou que toutes les cases aient été lues. Elle est aussi appelée recherche par balayage.
Principe[modifier | modifier le code]
La recherche séquentielle consiste à prendre les éléments de la liste les uns après les autres, jusqu'à avoir trouvé la cible, ou avoir épuisé la liste[1].
Complexité[modifier | modifier le code]
La complexité en temps est de O(n) pour le pire cas et en moyenne (pour une distribution uniforme). Elle est de O(1) pour la complexité dans le meilleur des cas.
Si les éléments de la liste sont classées par probabilités de requête décroissantes, et que ces probabilités suivent une loi géométrique alors la complexité en moyenne sera constante.
Comparaison[modifier | modifier le code]
Sur les tableaux triés, la recherche dichotomique est beaucoup plus rapide dans le pire des cas (logarithmique). Si les données sont en plus régulièrement espacées, alors la recherche par interpolation est encore plus efficace.
Notes et références[modifier | modifier le code]
- Frédéric Junier, « Recherche en table par balayage »
Liens externes[modifier | modifier le code]
- Jean-Jacques Lévy, « La recherche séquentielle », sur École polytechnique (France)
