Recherche séquentielle - Recherche NSI

Principe

linéaire

On parcourt le tableau de gauche à droite (ou de droite à gauche) jusqu'à trouver la valeur cherchée ou jusqu'à la fin.

Précondition

Aucune : le tableau peut être non trié

Une comparaison

À chaque indice : « est-ce égal à la cible ? »

Arrêt

Dès que trouvé, ou après n tests si absent

Indice renvoyé

Position trouvée, ou −1 / None si absent

À retenir

Les deux codes complets sont dans la section Les deux exemples Python ci-dessous.

Complexité T(n) et O(n)

pire cas

Soit n = len(tab).

Meilleur cas

Valeur en première position → 1 comparaison → T(n) = 1 → O(1)

Pire cas

Valeur absente ou en dernière position → n comparaisons → T(n) = n

Notation

Complexité linéaire au pire : O(n)

Cas moyen (idée)

Si la cible est équiprobable à chaque position → environ n/2 comparaisons

Avantages

pourquoi l'utiliser

La méthode la plus simple et la plus universelle.

Simplicité

Facile à coder et à expliquer en pseudo-code

Pas de tri requis

Fonctionne sur n'importe quel ordre des valeurs

Petites listes

Très bien pour n petit (quelques dizaines d'éléments)

Structures chaînées

Adapté aux listes chaînées (pas d'accès direct au milieu)

Inconvénients

limites

Devient lent quand n est grand.

Lent sur gros volumes

O(n) : 1 million d'éléments → jusqu'à 1 million de tests

Pas d'exploitation d'un tri

Même si le tableau est trié, on ne gagne rien

Recherches répétées

Si on cherche souvent dans le même grand tableau trié, mieux vaut dichotomie

📋 Trace d'exécution (exemple)

Tableau [4, 8, 2, 9], cible 9 :

i=0 : 4 ≠ 9
i=1 : 8 ≠ 9
i=2 : 2 ≠ 9
i=3 : 9 = 9  → retourne 3

Cible 5 absente : 4 comparaisons, retourne −1.

💻 Les deux exemples Python

Même objectif : retourner l'indice de la cible, ou -1 si absente. Compare les deux implémentations côte à côte.

1. Recherche séquentielle (O(n))

Fonctionne sur un tableau non trié. On avance indice par indice.

recherche_sequentielle.py

def recherche_sequentielle(tab, cible):
    for i in range(len(tab)):
        if tab[i] == cible:
            return i
    return -1

# Tableau non trié possible
notes = [12, 15, 9, 18, 11]
print(recherche_sequentielle(notes, 18))  # 3
print(recherche_sequentielle(notes, 7))   # -1

2. Recherche dichotomique (O(log n))

Nécessite un tableau trié. On coupe l'intervalle en deux à chaque étape.

recherche_dichotomique.py

def dichotomie(tab, cible):
    g, d = 0, len(tab) - 1
    while g <= d:
        m = (g + d) // 2
        if tab[m] == cible:
            return m
        elif tab[m] < cible:
            g = m + 1
        else:
            d = m - 1
    return -1

# Tableau trié obligatoire
ages = [2, 5, 8, 12, 16, 21]
print(dichotomie(ages, 8))   # 2
print(dichotomie(ages, 10))  # -1