Recherche linéaire

1.1 Définition de la recherche linéaire

La recherche linéaire (également connue sous le nom de recherche séquentielle) est un algorithme de recherche d'un élément dans une liste ou un tableau, qui vérifie chaque élément séquentiellement jusqu'à trouver une correspondance ou jusqu'à ce que tous les éléments aient été vérifiés. C'est l'algorithme de recherche le plus simple, qui ne nécessite pas de tri préalable des données.

Principes de base :

• Vérification séquentielle : L'algorithme passe par chaque élément du tableau ou de la liste, le comparant à la valeur recherchée.
• Arrêt de la recherche : La recherche s'arrête lorsque l'élément correspondant à la valeur recherchée est trouvé, ou lorsque tous les éléments ont été vérifiés.
• Ne nécessite pas de tri : La recherche linéaire peut être appliquée à des données non triées.
• Application : La recherche linéaire peut être appliquée à toutes les structures de données qui supportent l'itération, y compris les listes et les tableaux.

La recherche linéaire a une complexité temporelle de O(n), où n est le nombre d'éléments dans le tableau ou la liste. Dans le pire des cas, l'algorithme devra vérifier tous les n éléments pour trouver la valeur recherchée ou déterminer son absence.

Analyse de la complexité temporelle :

• Meilleur cas (Best case) : L'élément est trouvé en premier, O(1).
• Cas moyen (Average case) : L'élément est trouvé quelque part au milieu, O(n/2), ce qui est équivalent à O(n).
• Pire des cas (Worst case) : L'élément est trouvé en dernier lieu, ou est absent, O(n).

1.2 Implémentation pas à pas de la recherche linéaire

Étapes de la recherche linéaire :

• Initialisation : Définir l'indice de départ pour la recherche (généralement l'indice zéro).
• Vérification séquentielle : Vérifier chaque élément de la liste ou du tableau pour voir s'il correspond à la valeur recherchée.
• Condition de fin : Si l'élément est trouvé, retourner son indice. Si tous les éléments ont été vérifiés et que la valeur recherchée n'est pas trouvée, retourner une valeur spéciale (généralement -1 ou None).

Implémentation de la recherche linéaire en Python :

def linear_search(arr, target):
    # On parcourt chaque élément du tableau
    for index, element in enumerate(arr):
        # Si l'élément actuel est égal à la valeur recherchée, on retourne son indice
        if element == target:
            return index
    # Si l'élément n'est pas trouvé, on retourne -1
    return -1

Explication pas à pas de l'implémentation :

• Initialisation de la boucle : Une boucle for est utilisée avec la fonction enumerate, qui retourne l'indice et l'élément du tableau à chaque itération.
• Comparaison : À chaque itération, l'élément actuel est comparé à la valeur recherchée (target).
• Retour de l'indice : Si l'élément actuel est égal à la valeur recherchée, l'indice de cet élément est retourné.
• Retour de -1 : Si la boucle se termine et que l'élément recherché n'a pas été trouvé, -1 est retourné.

# Exemple d'utilisation :
arr = [4, 2, 7, 1, 9, 3]
target = 7
result = linear_search(arr, target)
print(f"Élément {target} trouvé à l'indice {result}")  # Sortie : Élément 7 trouvé à l'indice 2

# Exemple d'utilisation pour un élément qui n'est pas dans le tableau :
target = 5
result = linear_search(arr, target)
print(f"Élément {target} trouvé à l'indice {result}")  # Sortie : Élément 5 trouvé à l'indice -1

1.3 Exemples de problèmes résolus à l'aide de la recherche linéaire

La recherche linéaire est utilisée pour résoudre de nombreux problèmes liés à la recherche d'éléments dans des collections de données. Voici quelques exemples de ces problèmes :

Problème 1 : Recherche d'un élément dans un tableau

Il faut trouver un nombre donné dans un tableau de nombres.

Exemple :

def linear_search(arr, target):
    for index, element in enumerate(arr):
        if element == target:
            return index
    return -1

arr = [10, 23, 45, 70, 11, 15]
target = 70
index = linear_search(arr, target)
print(f"Élément {target} trouvé à l'indice {index}")  # Sortie : Élément 70 trouvé à l'indice 3

Problème 2 : Vérification de la présence d'un élément dans une liste

Il faut vérifier si une valeur donnée est présente dans une liste de chaînes de caractères.

Exemple :

def linear_search(arr, target):
    for element in arr:
        if element == target:
            return True
    return False

words = ["apple", "banana", "cherry", "date"]
target = "cherry"
found = linear_search(words, target)
print(f"Élément {target} {'trouvé' if found else 'non trouvé'}")  # Sortie : Élément cherry trouvé

Problème 3 : Recherche de l'élément minimum ou maximum

Il faut trouver la valeur minimale ou maximale dans une liste.

Exemple :

def find_min(arr):
    if not arr:
        return None
    min_val = arr[0]
    for element in arr:
        if element < min_val:
            min_val = element
    return min_val

arr = [34, 17, 23, 2, 45, 13]
min_value = find_min(arr)
print(f"Valeur minimale : {min_value}")  # Sortie : Valeur minimale : 2

Problème 4 : Recherche de la première occurrence

Il faut trouver la première occurrence d'un élément donné dans une liste.

Exemple :

def find_first_occurrence(arr, target):
    for index, element in enumerate(arr):
        if element == target:
            return index
    return -1

arr = [4, 2, 7, 1, 9, 3, 2]
target = 2
index = find_first_occurrence(arr, target)
print(f"Première occurrence de {target} à l'indice {index}")  # Sortie : Première occurrence de 2 à l'indice 1

Problème 5 : Comptage des occurrences

Compter le nombre d'occurrences d'un élément donné dans une liste.

Exemple :

def count_occurrences(arr, target):
    count = 0
    for element in arr:
        if element == target:
            count += 1
    return count

arr = [4, 2, 7, 2, 9, 3, 2]
target = 2
count = count_occurrences(arr, target)
print(f"Élément {target} rencontré {count} fois")  # Sortie : Élément 2 rencontré 3 fois