Le problème est le suivant : on dispose d'une liste comportant un nombre N d'éléments. Ces éléments ne sont pas forcément triés :
On souhaite savoir si une valeur particulière se trouve dans la liste. La méthode la plus simple consiste à vérifier si la première valeur de la liste est égale à la valeur recherché. Si ce n'est pas le cas, on passe à la case suivante, etc. Pour pouvoir regarder le contenu de chaque case de la liste, on utilise le fait que chacune des cases de la liste peut être adressée par un nombre compris entre 0 et la longueur de la liste moins un :
Attention : bien se rappeler que la première position d'une liste (ou d'un tuple, ou d'une chaîne de caractères) en Python est adressée par la valeur 0.
L'organigramme correspondant à cet algorithme est le suivant :
Ce qui en Python peut donner le code suivant :
def recherche(liste, elt):
"""
liste est une liste d'éléments, pas forcément triés.
elt est un élément dont on veut savoir s'il est ou non dans la liste.
La fonction renverra True si elt se trouve dans liste, False sinon.
"""
index = 0
while index < len(liste):
if liste[index] == elt:
return True
index = index + 1
return False
Une autre façon de faire serait d'utiliser une boucle for :
def recherche(liste, elt):
"""
liste est une liste d'éléments, pas forcément triés.
elt est un élément dont on veut savoir s'il est ou non dans la liste.
La fonction renverra True si elt se trouve dans liste, False sinon.
"""
for index in range(len(liste)):
if liste[index] == elt:
return True
return False Il existe une autre façon de parcourir une liste en Python avec une boucle for :
def recherche(liste, elt):
"""
liste est une liste d'éléments, pas forcément triés.
elt est un élément dont on veut savoir s'il est ou non dans la liste.
La fonction renverra True si elt se trouve dans liste, False sinon.
"""
for valeur in liste:
if valeur == elt:
return True
return False Dans ce cas, on adresse directement les éléments de liste, sans passer par leur numéro de case.
Ces trois codes sont équivalents en terme d'efficacité. La recherche peut être assez longue, surtout si la liste contient un grand nombre d'éléments.
Dans le pire des cas, si l'élément à chercher n'est pas présent dans la liste, l'algorithme devra effectuer N comparaisons. On peut donc dire que, dans le pire des cas, la complexité de cet algorithme est en O(N). On dit aussi que le coût de l'algorithme est linéaire. En d'autres termes, si on multiplie la taille de la liste par 10, le temps de recherche dans le pire des cas sera aussi multiplié par 10.
Il est difficile d'imaginer comment faire mieux avec un tableau dont les valeurs ne sont pas triées. Par contre, dans le cas où les valeurs seraient triées, on verra que l'algorithme de recherche dichotomique permet d'aller bien plus vite.
Exercice :
Faire une fonction comptage(liste, elt) qui doit renvoyer le nombre d’occurrences de "elt" dans "liste" (c'est-à-dire le nombre de fois où "elt" apparait dans "liste").
