La recherche dichotomique

Numérique et sciences informatiques

algorithme

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

dichotomie,algorithme,recherche

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.

Entrainement 1 :

Reproduire l'analyse précedente avec t = [5, 7, 12, 14, 23, 27, 35, 40, 41, 45] et x = 35

Voir une solution

Masquer

Programmation en python

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 ...

L’exécution du code doit donner :


>>> dichotomie([15, 16, 18, 19, 23, 24, 28, 29, 31, 33], 28)
True
>>> dichotomie([15, 16, 18, 19, 23, 24, 28, 29, 31, 33], 27)
False

Une visualisation de l'évolution des vraiables est disponible sur le site pythontutor

Terminaison et compléxité

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.

Entrainement 2 :

Déterminez le nombre maximal de comparaisons nécessaires à la recherche d'un élément dans une liste, encomplé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 compléxité en log(n). Comparer à l'algorithme de recherche séquentiel en O(n), C'est bien mieux en log(n). Vive la dichotomie !

Fiche de cours