Comparaisons
Correspondances
Reste à vérifier

  • Valeur cherchée
  • Comparées
  • Écartées
  • Trouvées

En savoir plus sur la recherche linéaire

Recherche linéaire

La recherche linéaire est la façon la plus simple de trouver une valeur : partir du début et vérifier chaque valeur tour à tour jusqu'à la trouver. Elle fonctionne sur n'importe quelle liste, triée ou non. Choisissez la valeur à chercher, lancez la recherche ou avancez d'une comparaison à la fois, et voyez comment le coût dépend de la position de la valeur, ou de sa présence même. Appuyez sur Lecture pour regarder la recherche, ou sur Étape et Retour pour avancer d'une comparaison à la fois. Faites glisser le curseur d'étapes pour aller n'importe où. La ligne pointillée marque la valeur cherchée. Choisissez la valeur, le nombre de barres, leur ordre de départ, ou saisissez vos propres nombres. Désactivez « Arrêter à la première correspondance » pour trouver toutes les correspondances. Quand le tableau est sélectionné, les flèches avancent d'une étape, la barre d'espace lance et met en pause, et Origine et Fin vont au début et à la fin.

Comment ça marche

  1. Choisissez la valeur à chercher, le nombre de barres et leur ordre de départ. Ou saisissez vos propres nombres.
  2. Appuyez sur Lecture, ou utilisez Étape et Retour pour avancer d'une comparaison à la fois. Faites glisser le curseur d'étapes pour aller n'importe où dans la recherche.
  3. Désactivez « Arrêter à la première correspondance » pour vérifier chaque valeur et trouver toutes les correspondances.

Comment fonctionne la recherche linéaire

Comparez la première valeur à la valeur cherchée. Si elles sont égales, c'est fini. Sinon, passez à la deuxième valeur, puis à la troisième, et ainsi de suite. Si vous atteignez la fin de la liste sans correspondance, la valeur cherchée n'est pas dans la liste. Rien à préparer : la liste n'a pas besoin d'être triée.

Combien de comparaisons

Une valeur à la position k est trouvée après k comparaisons. Dans le meilleur cas, une seule comparaison suffit, quand la valeur cherchée est en premier. Dans le pire cas, il en faut n, quand elle est en dernier ou absente, car ce n'est qu'après avoir vérifié chaque valeur qu'on peut être sûr qu'elle n'y est pas. En moyenne, pour une valeur présente dans la liste, il en faut environ (n + 1)/2. Pour une liste triée, la recherche dichotomique fait bien mieux : environ log₂ n comparaisons, soit 6 au lieu de 40 au plus pour 40 valeurs.

Questions fréquemment posées

Comment fonctionne la recherche linéaire ?

Elle vérifie les valeurs d'une liste une par une, de la première à la dernière, jusqu'à trouver la valeur cherchée ou épuiser les valeurs. On l'appelle aussi recherche séquentielle.

Quelle est la complexité en temps de la recherche linéaire ?

O(n) : dans le pire cas, quand la valeur cherchée est en dernier ou absente, elle la compare aux n valeurs. En moyenne, pour une valeur présente dans la liste, il faut environ (n + 1)/2 comparaisons.

Quand la recherche linéaire est-elle un bon choix ?

Pour les listes courtes, pour les listes non triées qu'on ne parcourt qu'une ou deux fois, et pour les données qu'on ne peut lire que dans l'ordre, comme un flux. Trier d'abord pour pouvoir utiliser la recherche dichotomique n'est rentable que si vous cherchez souvent.

Pourquoi une valeur absente coûte-t-elle le plus cher ?

Parce que rien ne dit à la recherche linéaire de s'arrêter plus tôt. Une correspondance ne peut être exclue qu'en vérifiant chaque valeur, donc une valeur absente de la liste demande toujours n comparaisons.

Mes nombres sont-ils envoyés quelque part ?

Non. La recherche s'exécute dans votre navigateur, et vos derniers réglages restent dans le stockage local de ce navigateur.

Prêt à l'essayer ?

Ouvrez PictorX dans votre navigateur – aucune installation, aucune carte de crédit requise pour démarrer.

Aller à l'éditeur