Avant de comprendre les différences entre la recherche linéaire et binaire, nous devons d'abord connaître séparément la recherche linéaire et la recherche binaire.
Qu'est-ce qu'une recherche linéaire ?
Une recherche linéaire est également connue sous le nom de recherche séquentielle qui analyse simplement chaque élément à la fois. Supposons que nous souhaitions rechercher un élément dans un tableau ou une liste ; nous calculons simplement sa longueur et ne sautons sur aucun élément.
Prenons un exemple simple.
Supposons que nous ayons un tableau de 10 éléments comme le montre la figure ci-dessous :
La figure ci-dessus montre un tableau de types de caractères comportant 10 valeurs. Si nous voulons rechercher 'E', alors la recherche commence à partir du 0èmeélément et analyse chaque élément jusqu'à ce que l'élément, c'est-à-dire « E » ne soit pas trouvé. Nous ne pouvons pas sauter directement du 0èmeélément au 4èmeélément, c'est-à-dire que chaque élément est analysé un par un jusqu'à ce que l'élément ne soit pas trouvé.
Complexité de la recherche linéaire
Comme la recherche linéaire analyse chaque élément un par un jusqu'à ce que l'élément ne soit pas trouvé. Si le nombre d'éléments augmente, le nombre d'éléments à scanner augmente également. On peut dire que le le temps nécessaire à la recherche des éléments est proportionnel au nombre d'éléments . Par conséquent, la complexité dans le pire des cas est O(n)
Qu'est-ce qu'une recherche binaire ?
Une recherche binaire est une recherche dans laquelle l'élément du milieu est calculé pour vérifier s'il est plus petit ou plus grand que l'élément à rechercher. Le principal avantage de l’utilisation de la recherche binaire est qu’elle n’analyse pas chaque élément de la liste. Au lieu de scanner chaque élément, il effectue la recherche sur la moitié de la liste. Ainsi, la recherche binaire prend moins de temps pour rechercher un élément par rapport à une recherche linéaire.
Celui pré-requis de la recherche binaire est qu'un tableau doit être trié, alors que la recherche linéaire fonctionne à la fois sur un tableau trié et non trié. L'algorithme de recherche binaire est basé sur la technique diviser pour régner, ce qui signifie qu'il divisera le tableau de manière récursive.
Il existe trois cas utilisés dans la recherche binaire :
Cas 1 : données
Cas 2 : data>a[mid] puis right=mid-1
Cas 3 : data = a[mid] // l'élément est trouvé
Dans le cas ci-dessus, ' un ' est le nom du tableau, milieu est l'indice de l'élément calculé de manière récursive, données est l'élément à rechercher, gauche désigne l'élément gauche du tableau et droite désigne l'élément qui apparaît sur le côté droit du tableau.
Comprenons le fonctionnement de la recherche binaire à travers un exemple.
Supposons que nous ayons un tableau de taille 10 indexé de 0 à 9, comme le montre la figure ci-dessous :
Nous voulons rechercher 70 éléments du tableau ci-dessus.
Étape 1: Tout d’abord, nous calculons l’élément central d’un tableau. Nous considérons deux variables, c'est-à-dire gauche et droite. Initialement, gauche =0 et droite=9 comme indiqué dans la figure ci-dessous :
La valeur de l'élément intermédiaire peut être calculée comme suit :
Par conséquent, mid = 4 et a[mid] = 50. L'élément à rechercher est 70, donc a[mid] n'est pas égal à data. Le cas 2 est satisfait, c'est-à-dire data>a[mid].
Étape 2: Comme data>a[mid], la valeur de left est donc incrémentée de mid+1, c'est-à-dire left=mid+1. La valeur de mid est 4, donc la valeur de left devient 5. Nous avons maintenant un sous-tableau comme le montre la figure ci-dessous :
Là encore, la valeur médiane est calculée à l'aide de la formule ci-dessus et la valeur du milieu devient 7. Désormais, la valeur médiane peut être représentée comme suit :
Dans la figure ci-dessus, nous pouvons observer que a[mid]>data, donc encore une fois, la valeur de mid sera calculée à l'étape suivante.
Étape 3: En tant que donnée[mid]>, la valeur de right est décrémentée de mid-1. La valeur de mid est 7, donc la valeur de right devient 6. Le tableau peut être représenté comme suit :
La valeur de mid sera calculée à nouveau. Les valeurs de gauche et de droite sont respectivement 5 et 6. Par conséquent, la valeur de mid est 5. Le milieu peut désormais être représenté dans un tableau comme indiqué ci-dessous :
Dans la figure ci-dessus, nous pouvons observer qu'un[milieu]
Étape 4: En tant que[milieu] Maintenant, la valeur de mid est à nouveau calculée en utilisant la formule dont nous avons déjà discuté. Les valeurs de gauche et de droite sont respectivement 6 et 6, donc la valeur de milieu devient 6, comme le montre la figure ci-dessous : Nous pouvons observer dans la figure ci-dessus que a[mid]=data. La recherche est donc terminée et l’élément est trouvé avec succès. Voici les différences entre la recherche linéaire et la recherche binaire : Description La recherche linéaire est une recherche qui trouve un élément dans la liste en recherchant l'élément séquentiellement jusqu'à ce que l'élément soit trouvé dans la liste. D'un autre côté, une recherche binaire est une recherche qui trouve l'élément du milieu dans la liste de manière récursive jusqu'à ce que l'élément du milieu corresponde à un élément recherché. Fonctionnement des deux recherches La recherche linéaire commence la recherche à partir du premier élément et analyse un élément à la fois sans passer à l'élément suivant. D'un autre côté, la recherche binaire divise le tableau en deux en calculant l'élément central du tableau. Mise en œuvre La recherche linéaire peut être implémentée sur n'importe quelle structure de données linéaire telle qu'un vecteur, une liste simple chaînée, une liste double chaînée. En revanche, la recherche binaire peut être implémentée sur ces structures de données avec un parcours bidirectionnel, c'est-à-dire un parcours vers l'avant et vers l'arrière. Complexité La recherche linéaire est facile à utiliser, ou on peut dire qu'elle est moins complexe puisque les éléments d'une recherche linéaire peuvent être disposés dans n'importe quel ordre, alors que dans une recherche binaire, les éléments doivent être disposés dans un ordre particulier. Éléments triés Les éléments d'une recherche linéaire peuvent être disposés dans un ordre aléatoire. Il n'est pas obligatoire dans la recherche linéaire que les éléments soient classés dans un ordre trié. En revanche, dans une recherche binaire, les éléments doivent être classés par ordre trié. Il peut être disposé soit par ordre croissant, soit par ordre décroissant, et en conséquence, l'algorithme sera modifié. La recherche binaire utilisant un tableau trié, il est nécessaire d'insérer l'élément au bon endroit. En revanche, la recherche linéaire ne nécessite pas de tableau trié, de sorte que le nouvel élément peut être facilement inséré à la fin du tableau. Approche La recherche linéaire utilise une approche itérative pour trouver l’élément, elle est donc également connue sous le nom d’approche séquentielle. En revanche, la recherche binaire calcule l’élément central du tableau et utilise donc l’approche diviser pour mieux régner. Base de données La recherche linéaire ne convient pas aux grands ensembles de données. Si nous voulons rechercher l'élément, qui est le dernier élément du tableau, une recherche linéaire commencera la recherche à partir du premier élément et se poursuivra jusqu'au dernier élément, donc le temps nécessaire pour rechercher l'élément serait long. D’un autre côté, la recherche binaire convient à un ensemble de données volumineux car elle prend moins de temps. Vitesse Si l’ensemble de données est volumineux en recherche linéaire, le coût de calcul serait élevé et la vitesse deviendrait lente. Si l'ensemble de données est volumineux dans la recherche binaire, le coût de calcul serait moindre par rapport à une recherche linéaire et la vitesse devient rapide. Dimensions La recherche linéaire peut être utilisée sur un tableau unidimensionnel ou multidimensionnel, tandis que la recherche binaire ne peut être implémentée que sur un tableau unidimensionnel. Efficacité La recherche linéaire est moins efficace lorsque l’on considère les grands ensembles de données. La recherche binaire est plus efficace que la recherche linéaire dans le cas de grands ensembles de données. Examinons les différences sous forme de tableau. 
Différences entre la recherche linéaire et la recherche binaire
tableau d'octets en chaîne
Base de comparaison Recherche linéaire Recherche binaire Définition La recherche linéaire commence la recherche à partir du premier élément et compare chaque élément avec un élément recherché jusqu'à ce que l'élément ne soit pas trouvé. Il trouve la position de l'élément recherché en trouvant l'élément du milieu du tableau. Données triées Dans une recherche linéaire, les éléments n'ont pas besoin d'être classés par ordre trié. La condition préalable à la recherche binaire est que les éléments doivent être classés dans un ordre trié. Mise en œuvre La recherche linéaire peut être implémentée sur n'importe quelle structure de données linéaire telle qu'un tableau, une liste chaînée, etc. L'implémentation de la recherche binaire est limitée car elle ne peut être implémentée que sur les structures de données ayant un parcours bidirectionnel. Approche Elle est basée sur l'approche séquentielle. Il est basé sur l’approche diviser pour mieux régner. Taille Il est préférable pour les ensembles de données de petite taille. Il est préférable pour les ensembles de données de grande taille. Efficacité Cette méthode est moins efficace dans le cas d’ensembles de données de grande taille. Cette méthode est plus efficace dans le cas d’ensembles de données de grande taille. Pire scénario Dans une recherche linéaire, le pire des cas pour trouver l’élément est O(n). Dans une recherche binaire, le pire des cas pour trouver l'élément est O(log2n). Le meilleur cas de scenario Dans une recherche linéaire, le meilleur scénario pour trouver le premier élément de la liste est O(1). Dans une recherche binaire, le meilleur scénario pour trouver le premier élément de la liste est O(1). Tableau dimensionnel Il peut être implémenté sur un tableau simple ou multidimensionnel. Il ne peut être implémenté que sur un tableau multidimensionnel.