La recherche linéaire et la recherche binaire sont des algorithmes communs utilisés pour trouver des éléments dans une liste. Comprendre le nombre de comparaisons que chaque algorithme fait peut aider à choisir la méthode la plus efficace pour des situations spécifiques. Cet article compare les comparaisons attendues dans les méthodes de recherche linéaires par rapport aux méthodes binaires.

Recherche linéaire

La recherche linéaire vérifie chaque élément de la liste de façon séquentielle jusqu'à ce qu'il trouve la cible ou atteigne la fin. Le nombre de comparaisons attendu dépend de la présence de la cible et de sa position dans la liste.

Si la liste contient des éléments n et que la cible est également susceptible d'être à n'importe quelle position, le nombre de comparaisons attendu est :

Comparaisons attendues = (n + 1) / 2

En effet, en moyenne, la recherche trouvera la cible à mi-chemin de la liste.

Recherche binaire

La recherche binaire fonctionne sur les listes triées en divisant à plusieurs reprises l'intervalle de recherche en deux. Son efficacité dépend de la taille de la liste et de la position de la cible.

Dans le meilleur des cas, la cible est au milieu, nécessitant une seule comparaison. Dans le pire des cas, il faut environ log2[[F1][F1][F1][F[

Si l'objectif est également susceptible d'être atteint, le nombre de comparaisons prévu est approximativement le suivant :

Comparaisons attendues -Log2 n[

Résumé de la comparaison

  • La recherche linéaire a un nombre de comparaison prévu de (n + 1) / 2.
  • La recherche binaire a un nombre de comparaison prévu d'environ log2 n.
  • La recherche binaire nécessite généralement moins de comparaisons pour les grandes listes.
  • La recherche linéaire peut être préférable pour les listes de petites ou non-triées.