Recherche linéaire en Python : Guide du débutant avec exemples

En ce qui concerne les algorithmes de recherche, la recherche linéaire est l'un des plus simples. Si vous avez déjà parcouru une liste d'articles un par un jusqu'à ce que vous trouviez ce que vous cherchiez, vous avez déjà effectué une recherche linéaire !

En plus d'être facile à comprendre, la recherche linéaire est utile parce qu'elle fonctionne sur des données non triées, contrairement à d'autres algorithmes de recherche. Cette polyvalence en fait une option utile dans les scénarios où le tri des données n'est pas possible. Je vais utiliser Python dans ce tutoriel, donc si, avant de commencer, vous voulez une remise à niveau sur Python, consultez le parcours de compétences Programmation en Python.

Qu'est-ce que la recherche linéaire ?

La recherche linéaire est un algorithme qui localise une valeur spécifique dans une liste en vérifiant chaque élément un par un. Il commence par le premier élément, le compare à la cible, puis continue à se déplacer dans la liste jusqu'à ce qu'il trouve la cible ou qu'il atteigne la fin de la liste. Il s'agit d'un algorithme simple et intuitif.

La recherche linéaire n 'a pas besoin que les données soient triées pour fonctionner, c'est pourquoi elle est principalement utilisée dans des ensembles de données non triées. Il est donc utile dans les situations où le tri n'est pas pratique ou lorsque vous travaillez avec des données brutes. Toutefois, cet avantage a un coût : il n'est pas aussi efficace que d'autres algorithmes qui nécessitent des données pré-triées.

La recherche linéaire est idéale lorsque vous travaillez avec des ensembles de données relativement petits ou lorsqu'il n'est pas possible de trier les données. Le schéma ci-dessous en donne une explication simplifiée.

Choisir la recherche linéaire

Examinons les avantages et les inconvénients de ce produit : 

Pourquoi choisir Linear Search ?

Selon moi, la recherche linéaire présente trois avantages distincts :

Quand la simplicité est la clé

L'un des principaux avantages de la recherche linéaire est sa simplicité. L'algorithme est facile à comprendre et à mettre en œuvre. Vous n'avez pas à vous préoccuper de trier ou de diviser les données de manière complexe. Commencez simplement au début de la liste et vérifiez chaque élément jusqu'à ce que vous trouviez ce que vous cherchez.

Quand vous n'avez pas le temps de trier

Contrairement à d'autres algorithmes de recherche tels que la recherche binaire, la recherche linéaire ne nécessite pas que l'ensemble de données soit trié. Il est donc idéal lorsque vous avez besoin d'un moyen rapide de trouver quelque chose.

Quand vous avez besoin de polyvalence

Un autre avantage de la recherche linéaire est qu'elle est polyvalente. Il fonctionne non seulement avec les tableaux, mais aussi avec d'autres structures de données Python, comme les listes chaînées. Tant que vous pouvez accéder aux éléments de manière séquentielle, la recherche linéaire peut faire l'affaire. Il est suffisamment souple pour gérer différents types de données, des nombres aux chaînes de caractères, en passant par les objets.

Pourquoi réfléchir à deux fois à la recherche linéaire ?

Il y a une question à prendre en compte :

Quand l'efficacité compte

Le principal inconvénient de la recherche linéaire est son inefficacité, en particulier pour les grands ensembles de données. Sa complexité temporelle est O(n), ce qui signifie que dans le pire des cas, vous pourriez avoir à vérifier chaque élément de la liste ! Cela peut vraiment ralentir les choses si vous travaillez avec des milliers ou des millions d'entrées. Toutefois, pour les petits ensembles de données, cette inefficacité peut être négligeable.

Implémentation d'un algorithme de recherche linéaire en Python

En Python, il existe deux façons courantes d'écrire une recherche linéaire : la méthode itérative et la méthode récursive. Pour démontrer ces deux méthodes, créons d'abord un ensemble de données simple de 100 nombres sans doublons.

numbers = [12, 7, 19, 3, 15, 25, 8, 10, 42, 56, 77, 23, 89, 65, 33, 99, 14, 2, 37, 81,
           48, 64, 22, 91, 6, 40, 59, 87, 28, 53, 74, 9, 16, 39, 71, 93, 54, 32, 61, 27,
           35, 18, 49, 68, 83, 46, 57, 29, 95, 11, 26, 44, 78, 5, 66, 73, 41, 85, 31, 50,
           20, 63, 88, 34, 90, 60, 67, 4, 52, 36, 62, 80, 21, 84, 98, 13, 45, 69, 30, 38,
           47, 17, 92, 55, 70, 76, 82, 24, 43, 1, 100, 58, 96, 75, 97, 94, 86, 72, 51, 79]

Méthode itérative

L'approche itérative est probablement la manière la plus simple de comprendre la recherche linéaire. Vous parcourez la liste en boucle, en vérifiant chaque élément jusqu'à ce que vous trouviez la cible ou atteigniez la fin.

Tout d'abord, nous allons créer notre fonction :

1. Nous allons parcourir en boucle chaque élément de la liste arr.

2. Nous comparerons chaque élément à la cible.

3. Si nous trouvons une correspondance, nous renvoyons l'index où la cible a été trouvée.

4. Si nous terminons la boucle sans trouver la cible, nous renvoyons 1 pour indiquer que l'élément n'est pas présent.

def linear_search_iterative(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i  # Return the index if the target is found
    return -1  # Return -1 if the target is not found

Ensuite, nous allons exécuter notre fonction sur notre ensemble de données et imprimer le résultat :

# Run the function on the numbers list
target = 91
index = linear_search_iterative(numbers, target)

if index != -1:
    print(f"Target {target} found at index {index}")
else:
    print(f"Target {target} not found!")

En exécutant ce code, nous trouvons la valeur cible au 23ème élément.

Méthode récursive

La méthode récursive utilise une fonction qui s'appelle elle-même pour parcourir la liste. Chaque appel récursif traite un élément à la fois, puis passe à l'élément suivant. Cette opération se poursuit jusqu'à ce que la cible soit trouvée ou que la fin de la liste soit atteinte.

Créons notre fonction récursive :

1. Nous commencerons par vérifier le premier élément (à l'index 0).
2. Si la cible correspond, nous renvoyons l'index.
3. Si la cible ne correspond pas, nous appellerons la même fonction de manière récursive, mais en incrémentant l'index de 1 pour vérifier l'élément suivant.
4. La récursion se poursuit jusqu'à ce que nous trouvions la cible ou que nous atteignions la fin de la liste.

def linear_search_recursive(arr, target, index=0):
    if index >= len(arr):  # Base case: we've checked all elements
        return -1
    if arr[index] == target:  # Base case: target found
        return index
    return linear_search_recursive(arr, target, index + 1)  # Recursive case: check next element

Nous pouvons utiliser le même code que ci-dessus pour exécuter cette fonction et elle renvoie la même valeur d'index pour notre cible : 23.

Gardez à l'esprit que cette approche utilise plus de mémoire car chaque appel récursif ajoute une nouvelle couche à la pile d'appels. Consultez la rubrique Comprendre les fonctions récursives en Python pour en savoir plus sur la récursivité.

Complexité du temps et de l'espace

L'une des façons d'évaluer l'efficacité d'un algorithme consiste à examiner sa complexité en termes de temps et d'espace. Consultez le tutoriel Analyser la complexité du code grâce à Python pour découvrir les différentes façons de mesurer la complexité d'un algorithme.

Complexité temporelle

La complexité temporelle d'un algorithme se réfère à la façon dont le temps nécessaire à son exécution augmente en fonction de la taille de l'entrée. La complexité temporelle de la recherche linéaire est O(n), où n est le nombre d'éléments de la liste. Cela signifie que, dans le pire des cas, l'algorithme peut devoir vérifier chaque élément avant de trouver la cible (ou de déterminer que la cible ne se trouve pas dans la liste). Cette méthode est assez inefficace, en particulier pour les grands ensembles de données. C'est pourquoi la recherche linéaire est la plus efficace lorsque les ensembles de données sont plus petits et non triés, et que la recherche ne doit être effectuée qu'une seule fois.

Complexité de l'espace

La complexité spatiale d'un algorithme est une mesure de la quantité de mémoire dont il a besoin lorsque la taille de l'entrée augmente. La complexité spatiale de l'algorithme de recherche linéaire dépend de la méthode utilisée. Pour la méthode itérative, la complexité spatiale est O(1), ce qui signifie que l'algorithme nécessite une quantité constante de mémoire, quelle que soit la taille de la liste d'entrée. En effet, la version itérative ne nécessite pas de mémoire supplémentaire, hormis la liste d'entrée et quelques variables pour garder trace de l'indice actuel.

Pour la méthode récursive, la complexité spatiale est O(n), ce qui signifie que la mémoire requise croît linéairement avec la taille de la liste d'entrée. Cela est dû aux appels récursifs de la fonction, qui ajoutent des couches à la pile d'appels pour chaque élément de la liste. Une liste plus importante nécessite plus de mémoire pour stocker ces appels, ce qui rend l'approche récursive moins efficace en termes d'espace.

Applications concrètes de la recherche linéaire

Bien que la recherche linéaire ne soit pas l'algorithme le plus efficace pour les grands ensembles de données, elle a des applications pratiques dans de nombreux scénarios. Examinons quelques situations où la recherche linéaire est l'outil le mieux adapté.

Petits ensembles de données pour lesquels le tri n'est pas pratique

La recherche linéaire est souvent la solution que j'utilise lorsque j'ai affaire à de petits ensembles de données qui ne valent pas la peine de consacrer du temps ou des ressources au tri. Dans ces cas, la simplicité de la recherche linéaire peut s'avérer plus efficace que les frais généraux liés au tri des données pour les algorithmes de recherche plus complexes.

Trouver la première occurrence d'une cible

Un autre cas d'utilisation courant de la recherche linéaire est celui où vous devez trouver la première occurrence d'une valeur cible. Comme la recherche linéaire se déplace dans la liste un élément à la fois, elle trouve naturellement la première instance de la cible et renvoie sa position. Cela peut s'avérer particulièrement utile dans des cas tels que la recherche de la première apparition d'un caractère dans une chaîne de caractères.

Lorsqu'une installation minimale est nécessaire

Parfois, la simplicité de la recherche linéaire en fait la meilleure option. Par exemple, si vous recherchez rapidement des données que vous ne prévoyez pas de réutiliser ou si vous avez besoin d'une réponse rapide, la configuration minimale de la recherche linéaire peut vous faire gagner du temps.

Recherche linéaire vs. Autres algorithmes de recherche

La recherche linéaire n'est qu'un des nombreux algorithmes de recherche existants. Examinons deux autres algorithmes de recherche courants : la recherche binaire et la recherche par hachage.

Recherche linéaire et recherche binaire

La recherche binaire est un algorithme qui permet de trouver la position d'une valeur cible dans un tableau trié en divisant de façon répétée l'intervalle de recherche en deux. Sa complexité temporelle est de O(log n), ce qui la rend beaucoup plus efficace que la recherche linéaire. Cependant, il ne fonctionne que sur des données triées. Lorsque votre ensemble de données est trié, la recherche binaire est presque toujours le meilleur choix car elle réduit l'espace de recherche de moitié à chaque étape, réduisant ainsi considérablement le nombre de comparaisons nécessaires pour trouver la cible.

La recherche linéaire peut s'avérer plus appropriée lorsque vos données ne sont pas triées, car elle fonctionne sur n'importe quel ensemble de données, trié ou non. Cependant, avec une complexité temporelle de O(n), la recherche linéaire est beaucoup moins efficace sur les ensembles de données triées.

Recherche linéaire ou recherche par hachage

La recherche par hachage est une méthode qui utilise un tableau de hachage pour trouver rapidement un élément. Avec une complexité temporelle de O(1), elle est nettement plus rapide que la recherche linéaire ou binaire. Toutefois, cette rapidité a un coût : vous devez d'abord construire un tableau de hachage, ce qui nécessite à la fois du temps et de la mémoire supplémentaire. Les recherches par hachage sont plus efficaces lorsque vous devez effectuer plusieurs recherches dans des ensembles de données volumineux, de sorte que la configuration initiale soit rentabilisée au fil du temps.

En revanche, la recherche linéaire ne nécessite aucune configuration, ce qui en fait une option plus simple. C'est le meilleur choix lorsque vous n'avez besoin d'effectuer une recherche qu'une seule fois ou quelques fois seulement, lorsque le temps supplémentaire nécessaire à la mise en place d'une table de hachage n'est pas justifiable. La recherche linéaire peut également être plus efficace en termes d'espace, car vous n'avez pas besoin de stocker une table de hachage pour utiliser l'algorithme.

Les pièges les plus courants et comment les éviter

Bien que la recherche linéaire soit un algorithme simple, il faut se méfier de quelques erreurs courantes.

Erreurs d'itération

L'une des erreurs les plus fréquentes lors de la mise en œuvre d'une recherche linéaire est une erreur de type "off-by-one". Ce problème est dû au fait que l'itération a démarré ou s'est arrêtée à un mauvais index. Il est important de se rappeler que les listes Python sont indexées par zéro, ce qui signifie que le premier élément a un index de 0. Si vous oubliez cela, vous risquez de sauter accidentellement le premier élément ou d'itérer une étape trop loin, ce qui entraînera des résultats incorrects ou des erreurs.

Incompréhension de l'indice retourné

Un autre écueil fréquent est de ne pas comprendre ce que la fonction renvoie lorsque la cible n'est pas trouvée dans la liste. Par convention, de nombreux algorithmes de recherche (y compris la recherche linéaire) renvoient -1 pour indiquer que la cible n'est pas présente. Cependant, certains débutants peuvent penser qu'il renvoie None, False, ou une autre valeur, ce qui peut prêter à confusion lors de l'interprétation des résultats.

Quand ne pas utiliser la recherche linéaire

Comme nous l'avons mentionné précédemment, la recherche linéaire devient rapidement inefficace pour les grands ensembles de données. C'est pourquoi il est préférable de le réserver à de petits ensembles de données non triées ou à des recherches rapides et ponctuelles.

Conclusion

La recherche linéaire est l'une des méthodes de recherche les plus simples. Elle vérifie chaque élément d'une liste de manière séquentielle, ce qui la rend facile à comprendre et à mettre en œuvre. La recherche linéaire est un choix fiable pour des recherches rapides et ponctuelles sur de petits ensembles de données, en particulier lorsque les données ne sont pas triées.

Si vous vous intéressez aux algorithmes de recherche, consultez les autres articles de cette série : Recherche binaire en Python, Recherche en profondeur en Python et Recherche en profondeur en Python. Vous pouvez également être intéressé par AVL Tree : Complete Guide With Python Implementation et Introduction to Network Analysis in Python comme sujets plus avancés.