La méthode la plus simple pour rechercher un élément dans une liste consiste à parcourir séquentiellement la liste jusqu'à atteindre l'élément cherché. Si l'élément recherché est trouvé, sa position dans la liste est, dans ce cas, retournée par l'algorithme qui s'arrête alors qu'une valeur sentinelle, fixée par exemple à -1, est retournée en cas de recherche infructueuse. Le déroulement de cette méthode, appelée recherche séquentielle, est illustré par la figure ci-dessous:
Déroulement de la recherche séquentielle de l'élément 54 sur une liste d'entiers
A mesure que l'indice i progresse vers la droite de la liste, les éléments situés à sa gauche ont été comparés au nombre recherché sans succès et l'algorithme se termine lorsque l'indice atteint la position de l'élément cherché ou lorsqu'il atteint l'extrémité droite de la liste auquel cas une valeur sentinelle (par exemple -1) est retournée afin d'indiquer que l'élément cherché ne se trouve pas dans la liste. Si la liste est précédemment triée, remarquons qu'il n'est pas nécessaire de la parcourir entièrement si l'élément ne s'y trouve pas. Effet, si l'élément en cours de traitement est plus grand que l'élément cherché, le processus peut s'arrêter et conclure à l'absence de l'élément cherché dans la liste.
A vous de jouer !
En vous basant sur l'exemple présenté ci-dessus, répondez à chacun des points suivants:
Calculez le nombre de comparaisons nécessaires pour rechercher les éléments 35 et 50 dans chacune des deux listes suivantes:
Pour chacun des deux types de listes (aléatoire et triée), déterminez le nombre moyen de comparaisons nécessaires à la recherche d'un élément appartenant, respectivement n'appartenant pas, à une liste, si celle-ci comporte 100 ou n éléments.
Implémentez la recherche séquentielle en Python sur une liste aléatoire et sur une liste triée en vous basant sur le squelette téléchargeable ici.
Solution
Il s'agit de se déplacer d'un élément au suivant en commençant tout à gauche et de comparer chacun avec l'élément recherché. Si l'élément testé est égal à l'élément recherché, l'algorithme s'arrête et retourne la position de l'élément. Sinon, l'algorithme continue jusqu'à atteindre la fin de la liste. Dans le cas d'une liste non triée comme [91, 17, 2, 35, 54, 12, 44, 25, 77, 33], la recherche exige 4 comparaisons pour trouver la position de 35 et 10 comparaisons pour constater que 50 n'appartient pas à la liste. Dans le cas d'une liste triée comme [2, 12, 17, 25, 33, 35, 44, 54, 77, 91], les performances de l'algorithme peuvent être améliorée : si l'élément cherché est plus petit que l'actuel élément traité, l'algorithme
peut s'arrêter et conclure à l'absence de l'élément cherché. Ainsi, le nombre de comparaisons nécessaires pour trouver 35 dans la liste est de 7 (6 pour arriver jusqu'à 35 et 1 pour vérifier que 35 est bien l'élément cherché) et de 9 (8 pour arriver jusqu'à 54 et 1 pour conclure que 50 < 54 et donc que 50 n'est pas dans la liste) pour conclure que 50 n'appartient pas à la liste.
Pour une liste aléatoire, la recherche d'un élément présent exige en moyenne (n+1)/2 comparaisons si l'élément appartient à la liste et n comparaisons s'il en est absent. Par contre, pour une liste triée, l'algorithme peut être améliorée et exiger en moyenne (n+3)/2 comparaisons si l'élément est présent ou non dans la liste.
Solution de l'implémentation sur une liste aléatoire et sur une liste triée.
Algorithmes et structures de données
