La recherche dichotomique consiste à chercher un élément elmt, en supposant qu'il s'y trouve dans d'une liste triée maListeTriee. De la manière suivante :

  • On compare elmt à l'élément du milieu de la liste.
  • S'il est égal à elmt, on a fini.
  • Sinon, s'il est inférieur, il faut chercher dans la première moitié de la liste. On retourne à l'étape 1 avec la liste réduite.
  • S'il est supérieur, on fait de même avec la seconde moitié de la liste.

 

Cela donne par exemple pour chercher le nombre 19 :

[ 5 7 8 11 14 16 18 19 23 27 31 32 34 ]

19≠18 et 19>18 donc [ 19 23 27 31 32 34 ]

1927 et 19<27 donc [ 19 23 ]

19=19 on a trouvé l'élément

 

 

Traitement de recherche_dichotomique :

 

Entrèe : l'élément elmt à chercher, maListeTriee liste de nb nombres triés.

 

initialiser l’indice a du premier élément de la liste à 0 , l’indice b du dernier élément de la liste à nb-1 (taille de la liste - 1)

initialiser l’indice n de l’élément du milieu de la liste à la partie entière (a+b)//2

Tant que a < b finSi

Si maListeTriee[n] = elmt

Sortie : n

finSi

Ou_Si maListeTriee[n] > elmt :

b prend la valeur n-1

finOu_Si

Sinon

a prend la valeur n-1

finSinon

n =(a+b)//2

fin>Tant que

Sortie :a

 

Cela donne en Python :

 


def recherche_dichotomique( elmt, maListeTriee ):
	a = 0 
	# a :indice du premier élément de la liste
	b = len(maListeTriee)-1
	# b : indice du dernier élément de la liste
	n = (a+b)//2
	# n : indice de l’élément du milieu de la liste
	while a ‹ b :
		if maListeTriee[n] == elmt :
			return n
			# renvoie n si l’élément elmt cherché est l’élément du milieu de la liste
		elif maListeTriee[n] › elmt :
			b = n-1
			# l’indice du nouveau dernier élément devient l’indice juste avant n si maListeTriee[n] › elmt
		else :
			a = n+1
			# sinon l’indice du nouveau premier élément devient l’indice juste après n
		n = (a+b)//2 
		# n prend la valeur n = (a+b)//2, milieu de la nouvelle sous-liste
	return a
	# renvoie a si la dernière sous liste contient 2 éléments et que celui recherché n’est pas le premier des deux (la boucle s’exécute tant que a<b)
# Cela suppose que l'élément cherché soit bien dans la liste

Free Joomla! template by L.THEME