Qu'est-ce qu'une recherche linéaire ?

Question

Accepted Answer

**Linear search** balaye une collection élément par élément jusqu'à ce qu'elle trouve la cible ou atteigne la fin. Elle fonctionne sur **n'importe quelle** liste — triée ou non — mais s'exécute en temps **O(n)**.

## L'idée

Aucune hypothèse sur l'ordre : vérifiez simplement chaque élément un à la fois.

## Exemple

```python
def linear_search(arr, target):
    for i, value in enumerate(arr):   # walk left to right
        if value == target:
            return i                  # return the index when found
    return -1                         # not found after full scan

linear_search([4, 2, 7, 1], 7)        # -> 2
```

## Complexité

- **Temps:** O(n) pire cas (cible dernière ou absente), O(1) meilleur cas.
- **Espace:** O(1).

## Quand l'utiliser

- Les données sont **non triées** et vous ne pouvez pas vous permettre de les trier.
- La liste est petite, donc O(n) est négligeable.
- Vous avez besoin d'une recherche ponctuelle où construire un index ou trier d'abord ne vaut pas la peine.

Si vous cherchez de manière répétée, préférez un tableau trié avec une recherche binaire ou un ensemble hash pour des recherches moyennes O(1).

## Pourquoi c'est important

La recherche linéaire est la base par rapport à laquelle tous les autres algorithmes de recherche sont mesurés.

Elle vous rappelle que le *bon* algorithme dépend des données : non trié et minuscule favorise le balayage simple ; grand et interrogé à plusieurs reprises favorise des structures plus intelligentes.

Savoir quand O(n) est suffisant empêche l'optimisation prématurée.