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 !
L'algorithme de dichotomie (aussi appelé recherche dichotomique) est une technique efficace pour trouver la position d'un élément dans une liste triée. Voici les étapes clés de cet algorithme :
Déterminer l'élément à rechercher.
Définir une plage de recherche en déterminant le premier et le dernier index de la liste.
Tant que la plage de recherche n'est pas vide, répéter les étapes suivantes :
Trouver l'index de l'élément situé au milieu de la plage de recherche.
Si l'élément du milieu correspond à l'élément recherché, renvoyer son index.
Sinon, si l'élément du milieu est plus grand que l'élément recherché, réduire la plage de recherche à la première moitié de la plage.
Sinon, l'élément du milieu est plus petit que l'élément recherché, réduire la plage de recherche à la deuxième moitié de la plage.
Si l'élément n'a pas été trouvé après avoir parcouru toute la liste, renvoyer -1.
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):
"""
Cherche l'élément dans une liste triée en utilisant l'algorithme de recherche dichotomique.
Args:
liste (list): La liste triée dans laquelle chercher l'élément.
element (int): L'élément à chercher dans la liste.
Returns:
int: L'index de l'élément dans la liste, ou -1 s'il n'est pas trouvé.
"""
# Initialisation de la plage de recherche
debut, fin = 0, len(liste)-1
# Tant que la plage de recherche n'est pas vide, continuer la recherche
while debut <= fin:
# Trouver l'index de l'élément situé au milieu de la plage de recherche
milieu = (debut + fin) // 2
# Si l'élément du milieu correspond à l'élément recherché, renvoyer son index
if liste[milieu] == element:
return milieu
# Sinon, si l'élément du milieu est plus grand que l'élément # recherché, réduire la plage de recherche à la première moitié de la plage
elif liste[milieu] < element:
debut = milieu + 1
# Sinon, l'élément du milieu est plus petit que l'élément
# recherché, réduire la plage de recherche à la deuxième moitié de la plage
else:
fin = milieu - 1
# Si l'élément n'a pas été trouvé après avoir
# parcouru toute la liste, renvoyer -1
return -1
