Nous avons déjà eu l'occasion d'étudier un algorithme de recherche d'un entier dans un tableau. Dans le pire des cas (l'entier recherché n'est pas dans le tableau), l'algorithme parcourt l'ensemble du tableau, nous avions donc une complexité O(n).
Est-on obligé de parcourir l'ensemble du tableau pour vérifier qu'un entier x ne se trouve pas dans un tableau t ? A priori oui, sauf si le tableau t est trié !
Jeu devine un nombre
Sans le savoir, vous avez déjà utilisé la dichotomie pour jouer au jeu devine un nombre (projet 2 de NSI). La meilleure stratégie était de couper en deux à chaque fois l'intervalle d'étude. On démarre de 50, puis 75 ou 25, etc.
On appelle cela une méthode par dichotomie , du grec ancien διχοτομία, dikhotomia (« division en deux parties »). La méthode de dichotomie fait partie des méthodes dites «diviser pour mieux régner».
Algorithme de recherche dichotomique
Le principe :
on se place au milieu de la liste.
on regarde si on est inférieur ou supérieur à la valeur cherchée.
on ne garde que la bonne moitié de la liste qui nous intéresse, et on recommence jusqu'à trouver la bonne valeur.
Exemple avec le tableau [2,4,6,7,8,9,10,19,21] et 7
Explications :
étape 1 : toute la liste est à traiter. On se place sur l'élément central. Son indice est la partie entière de la moitié de la longueur de la liste. Ici il y a 9 éléments, donc on se place sur l'élément d'indice 4, qui est 8.
étape 2 : on compare 8 à la valeur cherchée (7). Il faut donc garder tout ce qui est inférieur à 8.
étape 3 : on se place au milieu de la liste des valeurs qu'il reste à traiter. Ici il y a 4 valeurs, donc il n'y a pas de valeur centrale. On va donc se positionner sur l'élément d'indice 2, qui est 6.
étape 4 : on compare la valeur 6 à la valeur cherchée : 7. Elle est inférieure, donc on garde ce qui est à droite. Il n'y a plus qu'une valeur
étape 5 : on se place sur la valeur 7 et on compare avec 7. La valeur est trouvée.
Entraînement 1 :
Reproduire l'analyse précédente avec t = [5, 7, 12, 14, 23, 27, 35, 40, 41, 45] et x = 35
Soit tab un tableau non vide d'entiers triés dans l'ordre croissant et x un entier.
La fonction dichotomie ci-dessous doit renvoyer True si tab contient x et False sinon.
Les paramètres de la fonction sont :
tab, le tableau dans lequel s'effectue la recherche ;
x, l'entier à chercher dans le tableau ;
Recopier et compléter sous Python la fonction suivante en respectant la spécification.
def dichotomie(tab, x):
"""
tab : tableau d’entiers trié dans l’ordre croissant
x : nombre entier
La fonction renvoie True si tab contient x et False sinon
"""
debut = 0
fin = len(tab) - 1
while debut <= fin:
m = ...
if x == tab[m]:
return ...
if x > tab[m]:
debut = m + 1
else:
fin = ...
return ...
Une visualisation de l'évolution des variables est disponible sur le site pythontutor
Terminaison et complexité
La fonction Recherche_dichotomique contient une boucle non bornée, une boucle while, et pour être sûr de toujours obtenir un résultat, il faut s’assurer que le programme se termine, que l’on ne reste pas bloqué infiniment dans la boucle. Pour prouver que c’est bien le cas, nous allons utiliser un variant de boucle.
On appelle variant de boucle une quantité entière qui :
est positive ou nulle lorsque l'on reste dans la boucle;
décroît strictement à chaque itération de la boucle.
Un variant de boucle sert à prouver la terminaison d'une boucle, c'est-à-dire que l’on sort nécessairement de la boucle au boût d’un nombre fini d’itérations.
On dit que la valeur fin - debut représente le variant de boucle de cet algorithme. Ce variant est un nombre entier, d'abord strictement positif, puis qui va décroître jusqu'à la valeur 0. la valeur fin - debut est strictement décroissante, l'algorithme va donc s’arrêter.
Entraînement 2 :
Déterminez le nombre maximal de comparaisons nécessaires à la recherche d'un élément dans une liste, en complétant le tableau ci-dessous.
Taille de la liste
0
1
2
4
8
16
32
64
128
N
Recherche séquentielle
Recherche dichotomique
La complexité en log(n). Comparer à l'algorithme de recherche séquentiel en O(n), C'est bien mieux en log(n). Vive la dichotomie !
La recherche dichotomique est un algorithme efficace pour trouver un élément dans une liste triée. Elle consiste à diviser la plage de recherche en deux à chaque étape, en comparant l'élément recherché avec l'élément du milieu.
Principe de l’algorithme
Identifier l’élément à rechercher.
Définir la plage de recherche avec deux indices : début et fin.
Répéter tant que début ≤ fin :
Calculer l’indice du milieu : (début + fin) // 2
Si l’élément du milieu est égal à celui recherché → retourner l’indice.
Si l’élément du milieu est inférieur à celui recherché → chercher dans la deuxième moitié (début = milieu + 1).
Si l’élément du milieu est supérieur à celui recherché → chercher dans la première moitié (fin = milieu - 1).
Si l’élément n’est pas trouvé, retourner -1.
⚠️ Remarque : L’algorithme ne fonctionne que si la liste est triée!
Voici un exemple d'implémentation en Python de l'algorithme de dichotomie pour rechercher un élément dans une liste :
def recherche_dichotomique(liste, element):
"""
Recherche un élément dans une liste triée en utilisant la dichotomie.
Args:
liste (list): Liste triée dans laquelle chercher.
element (int): Élément à rechercher.
Returns:
int: Index de l’élément s’il est trouvé, -1 sinon.
"""
debut = 0
fin = len(liste) - 1
while debut <= fin:
milieu = (debut + fin) // 2
if liste[milieu] == element:
return milieu
elif liste[milieu] < element:
debut = milieu + 1
else:
fin = milieu - 1
return -1
