8.1. Algorithmes de recherche¶
8.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)
Cell In[4], line 1
----> 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
8.1.2. Recherche par dichotomie 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
On peut également proposer une version récursive.
In [17]: def appartient_dicho_recursif(elt, lst):
....: if len(lst) == 1:
....: return elt == lst[0]
....: m = len(lst)//2
....: if elt == lst[m]:
....: return True
....: if elt < lst[m]:
....: return appartient_dicho_recursif(elt, lst[:m-1])
....: else:
....: return appartient_dicho_recursif(elt, lst[m+1:])
....: return False
....:
In [18]: appartient_dicho_recursif(13, [1, 3, 5, 7, 8, 10, 13, 14, 17, 19])
Out[18]: True
In [19]: appartient_dicho_recursif(18, [1, 3, 5, 7, 8, 10, 13, 14, 17, 19])
Out[19]: False
8.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 [20]: lst = [5, -7, 4, -3, 2, 10]
In [21]: min(lst), max(lst)
Out[21]: (-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 [22]: 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 [23]: minmax([5, -7, 4, -3, 2, 10])
Out[23]: (-7, 10)
8.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 [24]: "pipa" in "pitapipapa"
Out[24]: True
In [25]: "tapa" in "pitapipapa"
Out[25]: False
La méthode index permet de renvoyer l’indice du caractère où a été trouvé le motif le cas échéant.
In [26]: "pitapipapa".index("pipa")
Out[26]: 4
In [27]: "pitapipapa".index("tapa")
---------------------------------------------------------------------------
ValueError Traceback (most recent call last)
Cell In[27], line 1
----> 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 [28]: def recherche_chaine(chaine, motif):
....: n = len(chaine)
....: m = len(motif)
....: for ind in range(n-m+1):
....: nb = 0
....: while nb < m and chaine[ind+nb] == motif[nb]:
....: nb +=1
....: if nb == m:
....: return True
....: return False
....:
In [29]: recherche_chaine("pitapipapa", "pipa")
Out[29]: True
In [30]: recherche_chaine("patapipapa", "tapa")
Out[30]: False
Succès
Echec
On peut à nouveau proposer une version de l’algorithme qui renvoie l’indice de la première occurence rencontrée.
In [31]: 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 [32]: indice_chaine("pitapipapa", "pipa")
Out[32]: 4
In [33]: indice_chaine("patapipapa", "tapa") # L'interpréteur IPython n'affiche pas None
Notes