Recherche dans un Tableau

Problème classique : "Cet élément existe-t-il dans la liste ?"

1. Recherche séquentielle

On parcourt chaque élément jusqu'à trouver la valeur.

POUR CHAQUE element DANS liste:
    SI element == 583:
        trouver()

Complexité : O(n). Au pire, on lit toute la liste.

2. Recherche dichotomique

Beaucoup plus rapide, mais nécessite une liste triée.

Principe :

1. Regarder l'élément du milieu
2. Éliminer la moitié impossible
3. Recommencer

Complexité : O(log n).

Conclusion : pour chercher vite, il faut souvent trier d'abord.