Dichotomie - Cours

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


from time import time
 
L=[ 1 ]*10**8



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

def recherchebuiltin(L,x) :
	tempsdepart=time()
	if x in L :
		return L.index(x),time()-tempsdepart
	else :
		return -1,time()-tempsdepart


x=int(input('Entrez un entier entre 1 et 100 : '))
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 entre 1 et 100 : 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.

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 L[(n-1)//2] et element.

Si L[(n-1)//2] est égal à element, la recherche est bien entendu terminée.
si n est pair et element < L[(n-1)//2], il nous restera à chercher element dans la liste [l₀, l₁, ..., l_(n-1)//2-1] qui contient n//2-1 éléments.
si n est pair et element > L[(n-1)//2], il nous restera à chercher dans la liste [l_(n-1)//2+1, l_(n-1)//2+2, ..., l_n-1] qui contient n//2 éléments.
si n est impair et element < L[(n-1)//2], il nous restera à chercher dans la liste [l₀, l₁, ..., l_(n-1)//2-1] qui contient n//2 éléments.
si n est impair et element > L[(n-1)//2], il nous restera à chercher dans la liste [l_(n-1)//2+1, l_(n-1)//2+2, ..., l_n-1] qui contient n//2 éléments.

La longueur initiale de la liste L étant n, on peut donc réduire -- en comparant un élément L[i] à element -- à au plus ⌊ n/2 ⌋ la longueur de liste dans laquelle chercher. (on rappelle que ⌊. ⌋ est la fonction partie entière et que ⌊ n/2 ⌋ est le quotient de la division entière de n par 2, c'est à dire n//2 en notation python).

Remarque : si la recherche est à mener entre les éléments L[a] et L[b] de la liste L, on compare L[(a+b)//2] à element, et si L[(a+b)//2] n'est pas égal à element, on cherche dans la liste [ l_a, ..., l_(a+b)//2-1] ou dans la liste [ l_(a+b)//2+1, ..., l_b] suivant les cas. On réduit ainsi, comme ci-dessus, la liste d'une longueur n à une longueur d'au plus n//2.

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.

Un point de détail.

Nous avons affirmé ci-dessus que la liste [l₀, l₁, ..., l_(n-1)//2-1] contient n//2 éléments si n est impair et n//2-1 éléments si n est pair.
Justifions ceci.

La liste [l₀, l₁, ..., l_(n-1)//2-1] contient (n-1)//2 éléments.

Si n est pair, n=2q (où q=n//2), d'où n-1=2q-1=2(q-1)+1 d'où (n-1)//2 = q-1 =n//2-1.
Si n est impair, n=2q+1 (où q=n//2) d'où n-1=2q et (n-1)//2 = q = n//2.

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 L[(a+b)//2]==element puis (en cas de non égalité) si L[(a+b)//2]<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]].

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.
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.
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.
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]=. On a L[7]<x. La recherche continue.
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.