Différence entre la recherche binaire et la recherche linéaire

Recherche binaire vs recherche linéaire

La recherche linéaire, également appelée recherche séquentielle, est l'algorithme de recherche le plus simple. Il recherche une valeur spécifiée dans une liste en vérifiant chaque élément de la liste. La recherche binaire est également une méthode utilisée pour localiser une valeur spécifiée dans une liste triée. La méthode de recherche binaire divise par deux le nombre d'éléments vérifiés (à chaque itération), ce qui réduit le temps nécessaire pour localiser l'élément donné dans la liste..

Qu'est-ce que la recherche linéaire??

La recherche linéaire est la méthode de recherche la plus simple. Elle vérifie séquentiellement chaque élément d’une liste jusqu’à ce qu’il trouve un élément spécifié. L'entrée dans la méthode de recherche linéaire est une séquence (telle qu'un tableau, une collection ou une chaîne) et l'élément à rechercher. La sortie est true si l'élément spécifié se trouve dans la séquence fournie ou false si ce n'est pas dans la séquence. Comme cette méthode vérifie chaque élément de la liste jusqu'à ce que l'élément spécifié soit trouvé, dans le pire des cas, elle passera en revue tous les éléments de la liste avant de trouver l'élément requis. La complexité de la recherche linéaire est o (n). Par conséquent, il est considéré comme trop lent pour être utilisé lors de la recherche d'éléments dans de grandes listes. Mais c'est très simple et facile à mettre en œuvre.

Qu'est-ce que la recherche binaire??

La recherche binaire est également une méthode utilisée pour localiser un élément spécifié dans une liste triée. Cette méthode commence par comparer l'élément recherché aux éléments situés au milieu de la liste. Si la comparaison détermine que les deux éléments sont égaux, la méthode s’arrête et renvoie la position de l’élément. Si l'élément recherché est supérieur à l'élément du milieu, la méthode est redémarrée en utilisant uniquement la moitié inférieure de la liste triée. Si l'élément recherché est inférieur à l'élément central, la méthode est redémarrée en utilisant uniquement la moitié supérieure de la liste triée. Si l'élément recherché ne figure pas dans la liste, la méthode renverra une valeur unique l'indiquant. Par conséquent, la méthode de recherche binaire divise par deux le nombre d'éléments comparés (à chaque itération), en fonction du résultat de la comparaison. Par conséquent, la recherche binaire s’exécute en temps logarithmique, ce qui se traduit par une performance de cas moyenne (log n).

Quelle est la différence entre la recherche binaire et la recherche linéaire?

Même si la recherche linéaire et la recherche binaire sont des méthodes de recherche, elles présentent plusieurs différences. Alors que la recherche binaire fonctionne sur des listes triées, la recherche de doublure peut également fonctionner sur des listes non triées. Le tri d’une liste a généralement une complexité de cas moyenne de n log n. La recherche linéaire est simple et simple à implémenter que la recherche binaire. Cependant, la recherche linéaire est trop lente pour être utilisée avec des listes volumineuses en raison de la performance moyenne de son cas (n). D'autre part, la recherche binaire est considérée comme une méthode plus efficace pouvant être utilisée avec des listes volumineuses. Mais mettre en œuvre la recherche binaire pourrait être assez délicat et une étude a montré que le code exact pour la recherche binaire ne pouvait être trouvé que dans cinq livres sur vingt..