Recherche lineaire

La recherche lineaire est la méthode la plus basique pour trouver un élément dans une liste. Tu parcours les éléments un par un, du debut a la fin, jusqu'a trouver ce que tu cherches.

C'est comme chercher une personne dans une file d'attente en regardant chaque personne une par une. Si la file a 100 personnes et que celle que tu cherches est la dernière, tu auras regarde 100 personnes. C'est O(n).

La recherche lineaire fonctionne sur n'importe quelle liste, triee ou non. C'est son avantage principal par rapport a la recherche binaire.

Écris une fonction recherche_lineaire(lst, cible) qui retourne l'index de cible dans lst, ou -1 si l'élément est absent.

Exemple :
recherche_lineaire([4, 2, 7, 1, 9], 7) renvoie 2
recherche_lineaire([4, 2, 7, 1, 9], 5) renvoie -1

Tests (3/4)

Élément trouve

assert recherche_lineaire([4, 2, 7, 1, 9], 7) == 2

Absent

assert recherche_lineaire([4, 2, 7, 1, 9], 5) == -1

Premier élément

assert recherche_lineaire([10, 20, 30], 10) == 0

+ 0 tests cachés

Indices (3 disponibles)

Solution officielle

def recherche_lineaire(lst, cible):
    for i, val in enumerate(lst):
        if val == cible:
            return i
    return -1

← Tri rapide (quick sort) Recherche binaire →

solution.py

Bravo!

Recherche lineaire

Tests (3/4)

Indices (3 disponibles)

Solution officielle