Recherche dichotomique
Nous avons déjà étudié des algorithmes de recherche d’élément dans un tableau : nous avions effectué une recherche séquentielle. Le parcours s’effectuait sur tout le tableau jusqu’à tomber sur l’élément recherché – s’il y figure bien entendu. Cet algorithme est dit naïf; en effet on ne cherche pas à optimiser l’efficacité. Sa complexité est linéaire: on peut estimer que le temps de recherche double lorsque la longueur de la liste double.
En utilisant une liste triée, l’algorithme de recherche dichotomique améliore l’efficacité en procédant comme suit :
L’idée centrale de cette approche repose sur l’idée de réduire de moitié l’espace de recherche à chaque étape : on regarde la valeur du milieu et si ce n’est pas celle recherchée, on sait qu’il faut continuer de chercher dans la première moitié ou dans la seconde.
Algorithme
On détermine m, élément au milieu du tableau ;
- si c’est la valeur recherchée, on s’arrête avec un succés ;
- sinon, deux cas sont possibles :
- si m est plus grand que la valeur recherchée, comme le tableau est trié, cela signifie qu’il suffit de continuer à chercher dans la première moitié du tableau ;
- sinon, il suffit de chercher dans la moitié droite.
- on répète cela jusque à avoir trouvé la valeur recherché, ou bien avoir réduit l’intervalle de recherche à un intervalle vide, ce qui signifie que la valeur recherchée n’est pas présente.
À chaque étape, on coupe l’intervalle de recherche en deux, et on en choisit une moitié. On dit que l’on procède par dichotomie, du grec dikha (en deux) et tomos (couper).
Le cours et les exercices (pdf): Recherche dichotomique-Cours
Vidéo sur la recherche dichotomique avec un tableau de suivi des variables (de la chaine « NSI à Mounier »):