5.1. Algorithmes de recherche

5.1.1. Recherche d’un élément dans une liste

Il faut noter que Python dispose déjà de l’opérateur in pour tester si un élément figure dans une liste.

In [1]: 2 in [5, 4, 1, 2, 3]
Out[1]: True

In [2]: 6 in [5, 4, 1, 2, 3]
Out[2]: False

La méthode index permet de renvoyer l’indice de l’élément dans la liste s’il a été trouvé.

In [3]: [5, 4, 1, 2, 3].index(2)
Out[3]: 3

In [4]: [5, 4, 1, 2, 3].index(6)
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
<ipython-input-4-b8fd51641ee1> in <module>()
----> 1 [5, 4, 1, 2, 3].index(6)

ValueError: 6 is not in list

On peut néanmoins proposer notre propre algorithme : il suffit de balayer la liste et de renvoyer True dès qu’on trouve l’élément recherché et False si on a parcouru toute la liste sans trouver l’élément.

In [5]: def appartient(elt, lst):
   ...:     for e in lst:
   ...:         if e == elt:
   ...:             return True
   ...:     return False
   ...: 

In [6]: appartient(2, [5, 4, 1, 2, 3])
Out[6]: True

In [7]: appartient(6, [5, 4, 1, 2, 3])
Out[7]: False

On peut également proposer une version qui renvoie l’indice la première occurence de l’élément recherché s’il est trouvé et None sinon.

In [8]: def indice(elt, lst):
   ...:     for i in range(len(lst)):
   ...:         if lst[i] == elt:
   ...:             return i
   ...:     return None
   ...: 

In [9]: indice(2, [5, 4, 1, 2, 3])
Out[9]: 3

In [10]: indice(6, [5, 4, 1, 2, 3])  # L'interpréteur IPython n'affiche pas None

5.1.2. Recherche d’un élément dans une liste triée

Lorsque l’on dispose d’une liste triée par ordre croissant, on peut grandement améliorer notre algorithme en utilisant le principe de dichotomie.

• On recherche tout d’abord l’élément central de la liste.
• Si c’est l’élément recherché, on s’arrête. Sinon, on le compare à l’élément recherché.
• Si l’élément recherché est inférieur à l’élément central, on le recherche dans la première partie de la liste. Sinon, on le recherche dans la deuxième partie de la liste.
• On retourne donc à la première étape de notre algorithme appliqué à l’une des deux demi-listes.

In [11]: def appartient_dicho(elt, lst):
   ....:     g = 0
   ....:     d = len(lst) - 1
   ....:     while g <= d:
   ....:         m = (g + d) // 2
   ....:         if lst[m] == elt:
   ....:             return True
   ....:         if elt < lst[m]:
   ....:             d = m - 1
   ....:         else:
   ....:             g = m + 1
   ....:     return False
   ....: 

In [12]: appartient_dicho(13, [1, 3, 5, 7, 8, 10, 13, 14, 17, 19])
Out[12]: True

In [13]: appartient_dicho(18, [1, 3, 5, 7, 8, 10, 13, 14, 17, 19])
Out[13]: False

Comme souvent, un dessin vaut mieux qu’un long discours. On donne deux exemples d’application de cet algorithme.

Recherche de 5 dans la liste [1, 3, 5, 7, 8, 10, 13, 14, 17, 19, 20]

Recherche de 13 dans la liste [1, 3, 5, 7, 8, 10, 13, 14, 17, 19]

A nouveau, on peut proposer une version qui renvoie l’indice de la première occurence de l’élément recherché plutôt qu’un booléen.

In [14]: def indice_dicho(elt, lst):
   ....:     g = 0
   ....:     d = len(lst) - 1
   ....:     while g <= d:
   ....:         m = (g + d) // 2
   ....:         if lst[m] == elt:
   ....:             return m
   ....:         if elt < lst[m]:
   ....:             d = m - 1
   ....:         else:
   ....:             g = m + 1
   ....:     return None
   ....: 

In [15]: indice_dicho(13, [1, 3, 7, 8, 10, 13, 14, 17, 19])
Out[15]: 5

In [16]: indice_dicho(18, [1, 3, 7, 8, 10, 13, 14, 17, 19])  # L'interpréteur IPython n'affiche pas None

Comparaison de l’efficacité des deux algorithmes

On peut comparer les temps de calcul des deux versions de l’algorithme de recherche d’un élément grâce à la commande magique %timeit : celle-ci permet d’exécuter un grand nombre de fois la même instruction et de mesurer le temps d’exécution moyen de cette instruction.

On remarque en particulier que le temps de calcul avec l’algorithme standard augmente à peu près proportionnellement à la taille de la liste tandis que le temps de calcul avec l’algorithme par dichotomie augmente très peu avec la taille de la liste. Le gain de temps de calcul est donc d’autant plus grand que la liste est grande [1]. On donnera une comparaison quantitative de ces deux temps de calcul dans le chapitre sur la complexité.

5.1.3. Recherche du maximum ou du minimim d’une liste

On suppose qu’on dispose d’une liste d’éléments que l’on peut comparer les uns aux autres et on cherche à déterminer le plus grand ou le plus petit élément. Python dispose déjà de deux fonctions min et max pour effectuer cette tâche.

In [17]: lst = [5, -7, 4, -3, 2, 10]

In [18]: min(lst), max(lst)
Out[18]: (-7, 10)

On peut également proposer notre algorithme. Rien de bien difficile, il suffit de parcourir un à un les éléments de la liste et de comparer chaque élément au minimum ou maximum des éléments précédents.

In [19]: def minmax(lst):
   ....:     m, M = None, None
   ....:     for elt in lst:
   ....:         if m is None or m > elt:
   ....:             m = elt
   ....:         if M is None or M < elt:
   ....:             M = elt
   ....:     return m, M
   ....: 

In [20]: minmax([5, -7, 4, -3, 2, 10])
Out[20]: (-7, 10)

5.1.4. Recherche d’une sous-chaîne dans une chaîne de caractères

L’objectif est de retrouver une sous-chaîne (qu’on appellera motif) dans une chaîne de caractères. Par exemple, la chaîne "pitapipapa" contient le motif "pipa" mais pas le motif "tapi". Python propose déjà cette fonctionnalité à l’aide de l’opérateur in.

In [21]: "pipa" in "pitapipapa"
Out[21]: True

In [22]: "tapa" in "pitapipapa"
Out[22]: False

La méthode index permet de renvoyer l’indice du caractère où a été trouvé le motif le cas échéant.

In [23]: "pitapipapa".index("pipa")
Out[23]: 4

In [24]: "pitapipapa".index("tapa")
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
<ipython-input-24-3adb3dc6f3c0> in <module>()
----> 1 "pitapipapa".index("tapa")

ValueError: substring not found

On présente ici un algorithme naïf qui est assez peu efficace mais qui a le mérite d’être très facile à comprendre : on prend successivement chaque caractère de la chaîne comme point de départ et on compare les caractères de la chaîne et les caractères du motif à partir de ce point de départ.

In [25]: def recherche_chaine(chaine, motif):
   ....:     n = len(chaine)
   ....:     m = len(motif)
   ....:     for ind in range(n-m):
   ....:         nb = 0
   ....:         while nb < m and chaine[ind+nb] == motif[nb]:
   ....:             nb +=1
   ....:         if nb == m:
   ....:             return True
   ....:     return False
   ....: 

In [26]: recherche_chaine("pitapipapa", "pipa")
Out[26]: True

In [27]: recherche_chaine("patapipapa", "tapa")
Out[27]: False

Recherche du motif "pipa" dans la chaîne "pitapipapa"

On peut à nouveau proposer une version de l’algorithme qui renvoie l’indice de la première occurence rencontrée.

In [28]: def indice_chaine(chaine, motif):
   ....:     n = len(chaine)
   ....:     m = len(motif)
   ....:     for ind in range(n-m):
   ....:         nb = 0
   ....:         while nb < m and chaine[ind+nb] == motif[nb]:
   ....:             nb +=1
   ....:         if nb == m:
   ....:             return nb
   ....:     return None
   ....: 

In [29]: indice_chaine("pitapipapa", "pipa")
Out[29]: 4

In [30]: indice_chaine("patapipapa", "tapa")     # L'interpréteur IPython n'affiche pas None

Notes

[1]	Il ne faut cependant pas crier tout de suite au miracle. L’algorithme de recherche par dichotomie nécessite que la liste traitée soit auparavant triée. Et le tri est une opération qui nécessite un certain temps de calcul (plus élevé que celui de l’algorithme de recherche standard).