Dichotomie

Recherche dans une liste triée

Exposé du problème

On dispose d'une liste triée. On recherche dans cette liste la présence d'un élément.

Une résolution 'naïve'

Une première idée peut-être d'éplucher un à un les éléments de la liste et de retourner l'indice dès que l'on tombe sur l'élément cherché. On retournera par exemple -1 dans le cas où l'élément n'est pas trouvé après avoir épluché toute la liste.

Entrée :	une liste triée L et un élément x
Sortie :	un indice d'une occurrence de x dans L ou -1 si x n'est pas dans L

Traitement : 
			Pour j de 0 jusque longueur(L)-1 :
				si x==L[j] : retourner j
			Fin de boucle Pour
			Retourner -1 en sortie de boucle (cas où la boucle n'a rien retourné)

Soit en langage python :

# création d'une liste au hasard pour les tests
from random import randint
L = [ randint(1,100) for j in range(20) ]


def recherche(L,x) :
	for i,y in enumerate(L) :
		if y == x : return i
	return -1


print('Liste L : ', L)	
x = int(input('Entrez un entier entre 1 et 100 : '))
print()
print('Résultat de la fonction recherche.')
r = recherche(L,x)
if r == -1 :
	print('Elément absent.')
else :
	print("Elément trouvé à l'indice ", r, ".")  
print()


# avec les outils python pour vérif :
print('Résultat de la recherche avec les builtins python (pour contrôle).')
if x in L :
	print("Première occurence de l'élément : ", L.index(x),".")
else :
	print('Elément absent.')

Dans le cas où l'élément cherché n'est pas dans la liste, tous les éléments de la liste initiale sont testés.
Si une liste contient un million de nombres, il y aura donc un million de tests.

Un problème de temps

La fonction time() du module time permet de mesurer le temps d'exécution d'une instruction.

On l'utilise ci-dessous pour mesurer le rapport temps de recherche par notre premier algorithme / temps de recherche avec les fonctions builtin sur une longue liste dans le cas le plus défavorable, c'est à dire dans le cas où l'élément cherché n'est pas dans la liste initiale.

Pour cela, on enregistre tout d'abord l'heure au départ dans la variable tempsdepart. Le temps écoulé durant l'exécution de la fonction est ensuite récupéré en fin de fonction par time()-tempsdepart.

from time import time
 
L=[ 1 ]*10**8 # création d'une liste ayant 100 000 000 d'éléments



def recherche(L,x) :
	""" 
		recherche par un simple parcours de la liste, 
		dans l'ordre des indices des éléments dans la liste.
	"""
	tempsdepart = time()
	for i,y in enumerate(L) :
		if y == x : return i, time()-tempsdepart
	return -1,time()-tempsdepart

def recherchebuiltin(L,x) :
	""" 
		recherche par la fonction index() définie dans le langage python.
	"""
	tempsdepart = time()
	if x in L :
		return L.index(x),time()-tempsdepart
	else :
		return -1,time()-tempsdepart


x=int(input('Entrez un entier  : '))
print()
print('Résultat de la fonction recherche.')
r=recherche(L,x)
 
print("Elément trouvé à l'indice ", r, ".\n")  
 


# avec les outils python pour vérif :
print('Résultat de la recherche avec les builtins python.')
s=recherchebuiltin(L,x)
print("Première occurence de l'élément : ", s ,".")

# rapport de temps :
print(r[1]/s[1])

On obtient ici :

Entrez un entier : 0

Résultat de la fonction recherche.
Elément trouvé à l'indice  (-1, 10.023625373840332) .

Résultat de la recherche avec les builtins python.
Première occurence de l'élément :  (-1, 1.9945297241210938) .
5.025558282044318

Dans le cas envisagé ici, notre algorithme met donc 5 fois plus de temps pour conclure que les fonctions builtin de python. Il est donc clair que l'on doit pouvoir faire mieux.

Et ce d'autant plus que nous n'avons pas encore exploité l'hypothèse d'une liste initiale déjà triée.

Le principe de dichotomie (binary search).

Il s'agit maintenant de mener une recherche cherchant à exploiter le fait que la liste initiale est triée.

Milieu d'une liste.

On dispose d'une liste L=[l₀, l₁, ..., l_n-1]. Pour parler de l'élément milieu de la liste, on va distinguer deux cas.

• Cas 1 : n est impair.
  Par exemple L=[l₀, l₁, l₂] avec n = 3, ou L=[l₀, l₁, l₂, l₃, l₄,l₅, l₆] avec n = 7. Dans ce cas, on voit que définir un élément milieu de liste est sans ambiguité :
  • avec n = 3, l'élément milieu de liste est l'élément l₁,
  • avec n = 7, l'élément milieu de liste est l'élément l₃,
  • avec n = 2q +1 entier impair quelconque, l'élément milieu de liste est l'élément l_q (où q = quotient dans la division entière de n par 2, ou encore n//2 avec la notation python).
  On constate de plus que les deux sous-listes se trouvant de chaque côté de l'élément milieu contiennent le même nombre d'éléments (à savoir q = n//2 éléments) :
  • Avec n = 3, les deux sous-listes sont [l₀] et [l₂].
  • Avec n = 7, les deux sous-listes sont [l₀, l₁, l₂] et [l₄,l₅, l₆].
  • avec n = 2q +1 entier impair quelconque, les deux sous-listes sont [l₀, l₁, l₂, ..., l_q-1] et [l_q+1, l_q+2, l_q+3, ..., l_n-1] (cette seconde sous-liste contient (n-1)-(q+1)+1 = (2q+1-1)-(q+1)+1 = q éléments comme la première).
• Cas 2 : n est pair.
  Par exemple L=[l₀, l₁, l₂, l₃] avec n = 4, ou L=[l₀, l₁, l₂, l₃, l₄,l₅, l₆, l₇] avec n = 8. Dans ce cas, on voit que définir un élément milieu de liste est plus ambigu.
  On décide dans la suite d'appeler élément milieu de liste l'élément d'indice q où q est le quotient dans la division entière de n par 2, c'est à dire q = n//2 :
  • avec n = 4 = 2 × 2, l'élément milieu de liste est l'élément l₂,
  • avec n = 8 = 2 × 4, l'élément milieu de liste est l'élément l₄,
  • avec n = 2q entier impair quelconque, l'élément milieu de liste est l'élément l_q.
  Les deux sous-listes se trouvant de chaque côté de l'élément milieu ne contiennent pas dans ce cas le même nombre d'éléments :
  • Avec n = 4, les deux sous-listes sont [l₀, l₁] et [l₃].
  • Avec n = 8, les deux sous-listes sont [l₀, l₁, l₂,l₃] et [l₅,l₆, l₇].
  • avec n = 2q entier pair quelconque, les deux sous-listes sont [l₀, l₁, l₂, ..., l_q-1] (qui contient q éléments) et [l_q+1, l_q+2, l_q+3, ..., l_n-1] (cette seconde sous-liste contient (n-1)-(q+1)+1 = (2q-1)-(q+1)+1 = q-1 éléments).

Milieu d'une liste : second choix possible.

Comme les éléments de la liste sont numérotés de 0 à n-1, on pourrait vouloir choisir comme élément milieu l'élément q = (n-1)//2 (quotient de la division entière de n-1 par 2).

Lorsque n est impair, c'est en fait le même choix que ci-dessus (puisque n = 2q+1 est équivalent à n-1 = 2q : le quotient de la division entière de n par 2 est le même que le quotient de la division entière de n-1 par 2).

Dans le cas n = 2q pair, décider d'appeler élément milieu de liste l'élément d'indice (n-1)//2 revient à choisir l'élément d'indice q-1 (car q-1 est le quotient dans la division entière de n-1 par 2, en effet n = 2q peut aussi s'écrire n-1 = 2(q-1)+1).

• avec n = 4 = 2 × 2, l'élément milieu de liste serait alors l'élément l₁,
• avec n = 8 = 2 × 4, l'élément milieu de liste est l'élément l₃,
• avec n = 2q entier impair quelconque, l'élément milieu de liste est l'élément l_q-1.

et les effectifs des deux sous-listes restantes seraient respectivement de q-1 et q éléments :

• Avec n = 4, les deux sous-listes seraient [l₀ ] et [l₂,l₃].
• Avec n = 8, les deux sous-listes seraient [l₀, l₁, l₂ ] et [l₄, l₅,l₆, l₇].
• avec n = 2q entier impair quelconque, les deux sous-listes sont [l₀, l₁, l₂, ..., l_q-2] (qui contient q-1 éléments) et [l_q, l_q+2, l_q+3, ..., l_n-1] (cette seconde sous-liste contient (n-1)-(q)+1 = (2q-1)-(q)+1 = q éléments).

On généralise facilement ce choix lorsqu'il s'agit de parler du milieu de liste L = [ l_a, l _a+1, l_a+2,..., l_b]. On appellera dans ce cas milieu de liste, l'élément l_(a+b)//2.

Ce qu'il faut retenir de tout cela, c'est que l'on peut toujours choisir un élément "milieu" tel que les deux sous-listes restantes contiennent au plus q = n//2 éléments.

Diviser par 2 la longueur de liste dans laquelle on cherche.

On suppose disposer d'une liste initiale de longueur n : L=[l₀, l₁, ..., l_n-1] triée (en ordre croissant). On cherche element dans cette liste.

On compare element avec l'élément de milieu de liste (nommons le m).

1. Si m = element, la recherche est bien entendu terminée.
2. Si m < element, alors element ne peut se trouver que dans la demi-liste se trouvant après m.
3. Si m > element, alors element ne peut se trouver que dans la demi-liste se trouvant avant m.

Dans tous les cas, on voit qu'après une comparaison, soit on a terminé, soit la recherche aura ensuite lieu dans une liste contenant au plus q = n//2 (quotient de la division entière de n par 2) éléments.

Si l'on doit chercher element dans une liste de un million d'éléments, on peut donc après une comparaison à un élément réduire la recherche à une liste d'au plus 500 000 éléments.

Itérations

On itère bien sûr le procédé tant que element n'est pas trouvé et que la partie de liste restante n'est pas vide. Il paraît clair que le nombre de tests à effectuer sera bien moindre ainsi que par la méthode de recherche proposée dans le premier paragraphe.

Remarque. Dans ce qui précède, lorsqu'on écrit "une comparaison à un élément ", il s'agit en fait en général de deux tests de comparaisons : on teste d'abord si m == element (où m est l'élément milieu de liste) puis (en cas de non égalité) si m < element.

Dans la feuille d'exercices, vous aurez à programmer cette recherche et à rentrer un peu plus dans les détails du nombre de tests effectués pour une recherche.

Un exemple

Rechercher l'élément 50 dans la liste L=[2,5, 9, 15,20, 21, 32, 43]=[L[0],L[1],...,L[7]].

1. On cherche x=50 entre les éléments d'indice debut = 0 et fin = 7. Pour cela, on considère l'élément L[7//2] = L[3] = 15. On a L[3] < x. La recherche continue.
2. On cherche x=50 entre les éléments d'indice debut = 4 et fin = 7. Pour cela, on considère l'élément L[(7+4)//2] = L[5] = 21. On a L[5] < x. La recherche continue.
3. On cherche x = 50 entre les éléments d'indice debut = 6 et fin = 7. Pour cela, on considère l'élément L[(7+6)//2] = L[6] = 32. On a L[6] < x. La recherche continue.
4. On cherche x = 50 entre les éléments d'indice debut = 7 et fin = 7. Pour cela, on considère l'élément L[(7+7)//2] = L[7] = 43. On a L[7] < x. La recherche continue.
5. On cherche x = 50 entre les éléments d'indice debut = 8 et fin = 7. Comme debut>fin, on a en fait épluché toute la liste : l'élément est absent.