C1-ALGO-05.01 Algorithmes classiques (Recherche)
Contents
C1-ALGO-05.01 Algorithmes classiques (Recherche)#
Algorithmes de recherche#
Un algorithme de recherche consiste à trouver une cible parmi une liste d’éléments. Par exemple : la liste est : [1,4,67,34,109,69,23] et la cible 69.
Les algorithmes de recherche peuvent se classer en deux catégories:
Recherche dans des problèmes classiques
Recherche dans des problèmes complexes
S’agissant des problèmes complexes, les solutions dépassent le cadre de ce cours
Recherche séquentielle#
La recherche linéaire consiste à parcourir chaque élément de la liste et le comparer à la cible.
Recherche dichotomique#
La recherche dichotomique consiste à rechercher la cible dans la liste triée en divisant la liste par deux et en comparant la cible avec les deux éléments bornes des sous-listes. Si la cible est égale, l’algorithme s’arrête, sinon la recherche continue sur les moitiés de sous-listes.
A retenir#
Le meilleur algorithme pour rechercher une cible :
dans une liste non triée est d’ordre linéaire (il faut parcourir tous les éléments pour trouver la cible)
dans une liste triée est d’ordre logarithmique (on divise chaque fois par deux le nombre d’éléments pour trouver la cible)