Recherche linéaire (Linear Search)

Recherche linéaire (Linear Search)

Principe de l'algorithme

Cette approche ne fait aucune hypothèse sur l'ordre des éléments. Elle fonctionne aussi bien sur des tableaux triés que non triés.

Implémentations de la recherche linéaire

Version simple

FONCTION RechercheLineaire(tab, n, x):
    POUR i DE 0 À n-1 FAIRE
        SI tab[i] == x ALORS
            RETOURNER i   // Élément trouvé à l'indice i
        FINSI
    FINPOUR
    RETOURNER -1          // Élément non trouvé
FINFONCTION

def recherche_lineaire(tab, x):
    """
    Recherche linéaire d'un élément x dans un tableau.
    
    Paramètres:
        tab: tableau quelconque (trié ou non)
        x: élément recherché
    
    Retourne:
        L'indice de l'élément s'il est trouvé, -1 sinon
    """
    for i in range(len(tab)):
        if tab[i] == x:
            return i
    return -1


# Test
tab = [5, 2, 8, 3, 9, 1, 4, 7, 6]
x = 8

resultat = recherche_lineaire(tab, x)

if resultat != -1:
    print(f"L'élément {x} est présent à l'indice {resultat}")
else:
    print(f"L'élément {x} n'est pas présent dans le tableau")

#include <stdio.h>

int recherche_lineaire(int tab[], int n, int x) {
    for (int i = 0; i < n; i++) {
        if (tab[i] == x) {
            return i;  // Élément trouvé à l'indice i
        }
    }
    return -1;  // Élément non trouvé
}

int main() {
    int tab[] = {5, 2, 8, 3, 9, 1, 4, 7, 6};
    int n = sizeof(tab) / sizeof(tab[0]);
    int x = 8;
    
    int resultat = recherche_lineaire(tab, n, x);
    
    if (resultat != -1) {
        printf("L'élément %d est présent à l'indice %d\n", x, resultat);
    } else {
        printf("L'élément %d n'est pas présent dans le tableau\n", x);
    }
    
    return 0;
}

L'élément 8 est présent à l'indice 2

Version avec sentinelle (optimisation)

Une optimisation classique consiste à utiliser une sentinelle pour éviter de vérifier à chaque itération si on a atteint la fin du tableau. On place la valeur recherchée à la fin du tableau (en supposant qu'il y a de la place), ce qui garantit que la recherche trouvera toujours la valeur (soit la vraie, soit la sentinelle).

FONCTION RechercheLineaireSentinelle(tab, n, x):
    // Supposons que tab a une taille suffisante
    dernier = tab[n-1]
    tab[n-1] = x   // Placer la sentinelle
    
    i = 0
    TANT QUE tab[i] != x FAIRE
        i = i + 1
    FINTANTQUE
    
    tab[n-1] = dernier  // Restaurer la valeur originale
    
    SI i < n-1 OU tab[n-1] == x ALORS
        RETOURNER i
    SINON
        RETOURNER -1
    FINSI
FINFONCTION

def recherche_lineaire_sentinelle(tab, x):
    """
    Recherche linéaire avec sentinelle (optimisation).
    Note: Cette version modifie temporairement le tableau.
    """
    n = len(tab)
    dernier = tab[n-1]
    tab[n-1] = x  # Placer la sentinelle
    
    i = 0
    while tab[i] != x:
        i += 1
    
    tab[n-1] = dernier  # Restaurer la valeur originale
    
    if i < n-1 or tab[n-1] == x:
        return i
    return -1


# Test
tab = [5, 2, 8, 3, 9, 1, 4, 7, 6]
x = 8

resultat = recherche_lineaire_sentinelle(tab, x)

if resultat != -1:
    print(f"L'élément {x} est présent à l'indice {resultat}")
else:
    print(f"L'élément {x} n'est pas présent dans le tableau")

L'élément 8 est présent à l'indice 2

Exemples d'exécution pas à pas

  Exemple n°1 : Recherche de 8 dans [5, 2, 8, 3, 9, 1, 4, 7, 6]

  Exemple n°2 : Recherche de 10 dans le même tableau (non trouvé)

Analyse de complexité

Avantages et inconvénients

Comparaison : recherche linéaire vs dichotomique

Variantes et extensions

Recherche de toutes les occurrences

def rechercher_toutes_occurrences(tab, x):
    """
    Retourne une liste de tous les indices où x apparaît.
    """
    indices = []
    for i in range(len(tab)):
        if tab[i] == x:
            indices.append(i)
    return indices


# Test
tab = [5, 2, 8, 3, 8, 1, 8, 7, 6]
x = 8
print(f"Indices de {x} : {rechercher_toutes_occurrences(tab, x)}")

Indices de 8 : [2, 4, 6]

Recherche linéaire dans une liste chaînée

class Noeud:
    def __init__(self, valeur):
        self.valeur = valeur
        self.suivant = None

def rechercher_liste_chainee(tete, x):
    """
    Recherche linéaire dans une liste chaînée.
    """
    courant = tete
    position = 0
    
    while courant is not None:
        if courant.valeur == x:
            return position
        courant = courant.suivant
        position += 1
    
    return -1


# Création d'une liste chaînée : 5 → 2 → 8 → 3
tete = Noeud(5)
tete.suivant = Noeud(2)
tete.suivant.suivant = Noeud(8)
tete.suivant.suivant.suivant = Noeud(3)

print(f"Position de 8 : {rechercher_liste_chainee(tete, 8)}")

Position de 8 : 2

Recherche linéaire récursive

def recherche_lineaire_recursive(tab, x, i=0):
    """
    Version récursive de la recherche linéaire.
    """
    if i >= len(tab):
        return -1
    if tab[i] == x:
        return i
    return recherche_lineaire_recursive(tab, x, i + 1)


# Test
tab = [5, 2, 8, 3, 9, 1, 4, 7, 6]
x = 8
print(f"Indice de {x} : {recherche_lineaire_recursive(tab, x)}")

Indice de 8 : 2