La principale différence entre la recherche linéaire et la recherche binaire est que la recherche binaire prend moins de temps pour rechercher un élément dans la liste triée. On en déduit donc que l'efficacité de la méthode de recherche binaire est supérieure à la recherche linéaire.
Une autre différence entre les deux est qu’il existe une condition préalable à la recherche binaire, c’est-à-dire que les éléments doivent être triés, alors qu’en recherche linéaire, cette condition préalable n’existe pas. Bien que les deux méthodes de recherche utilisent des techniques différentes, décrites ci-dessous.
Tableau de comparaison
| Base de comparaison | Recherche linéaire | Recherche binaire |
|---|---|---|
| La complexité du temps | SUR) | O (log 2 N) |
| Meilleur temps | Premier élément O (1) | Élément central O (1) |
| Prérequis pour un tableau | Non requis | Le tableau doit être trié |
| Le pire cas pour N nombre d'éléments | N comparaisons sont nécessaires | Peut conclure après seulement 2 log de comparaison |
| Peut être implémenté sur | Tableau et liste chaînée | Ne peut pas être implémenté directement sur une liste chaînée |
| Opération d'insertion | Facilement inséré à la fin de la liste | Exiger que le traitement soit inséré à l'endroit approprié pour conserver une liste triée. |
| Type d'algorithme | De nature itérative | Diviser et conquérir dans la nature |
| Utilité | Facile à utiliser et pas besoin d'éléments commandés. | Quoi qu'il en soit, l'algorithme et les éléments difficiles doivent être organisés dans l'ordre. |
| Lignes de code | Moins | Plus |
Définition de la recherche linéaire
Dans une recherche linéaire, chaque élément d'un tableau est extrait un par un dans un ordre logique et vérifié s'il s'agit d'un élément souhaité ou non. Une recherche échouera si tous les éléments sont accédés et si l’élément souhaité n’est pas trouvé. Dans le pire des cas, il est possible que nous devions analyser la moitié de la taille du tableau (n / 2).
Par conséquent, la recherche linéaire peut être définie comme la technique qui parcourt le tableau séquentiellement pour localiser l'élément donné. Le programme donné ci-dessous illustre la recherche d'un élément du tableau à l'aide de la recherche.
Efficacité de la recherche linéaire
La consommation de temps ou le nombre de comparaisons effectuées lors de la recherche d'un enregistrement dans une table de recherche détermine l'efficacité de la technique. Si l'enregistrement souhaité est présent à la première position du tableau de recherche, une seule comparaison est alors effectuée. Lorsque l'enregistrement souhaité est le dernier, il faut effectuer n comparaisons. Si l’enregistrement doit figurer quelque part dans le tableau de recherche, le nombre de comparaisons sera en moyenne (n + 1/2). Le pire cas d'efficacité de cette technique est O (n) correspond à l'ordre d'exécution.
C Programme pour rechercher un élément avec la technique de recherche linéaire.
#include #include void main () {int a [100], n, i, élément, loc = -1; clrscr (); printf ("\ nEntrez le numéro d'élément:"); scanf ("% d", & n); printf ("Entrez les chiffres: \ n"); pour (i = 0; i <= n-1; i ++) {scanf ("% d", & a [i]); } printf ("\ nEntrez le numéro à rechercher:"); scanf ("% d", & item); pour (i = 0; i = 0) {printf ("\ n% d est trouvé à la position% d:", élément, loc + 1); } else {printf ("\ n L'élément n'existe pas"); } getch (); } Définition de la recherche binaire
La recherche binaire est un algorithme extrêmement efficace. Cette technique de recherche consomme moins de temps pour rechercher un élément donné en comparant le moins possible. Pour faire la recherche binaire, nous devons d’abord trier les éléments du tableau.
La logique derrière cette technique est donnée ci-dessous:
- Tout d'abord, trouvez l'élément du milieu du tableau.
- L'élément central du tableau est comparé à l'élément à rechercher.
Il y a trois cas possibles:
- Si l'élément est l'élément requis, la recherche est réussie.
- Lorsque l'élément est inférieur à l'élément souhaité, recherchez uniquement la première moitié du tableau.
- S'il est supérieur à l'élément souhaité, effectuez une recherche dans la seconde moitié du tableau.
Répétez les mêmes étapes jusqu'à ce qu'un élément soit trouvé ou épuise dans la zone de recherche. Dans cet algorithme, chaque zone de recherche est réduite. Par conséquent, le nombre de comparaisons est au plus logarithmique (N + 1). En conséquence, il s'agit d'un algorithme efficace par rapport à la recherche linéaire, mais le tableau doit être trié avant la recherche binaire.
C Programme pour trouver un élément avec une technique de recherche binaire.
#include void main () {int i, début, fin, milieu, n, recherche, array [100]; printf ("Entrez le nombre d'éléments \ n"); scanf ("% d", & n); printf ("Entrez les% d nombres \ n", n); pour (i = 0; i <n; i ++) scanf ("% d", & array [i]); printf ("Entrez le numéro à rechercher \ n"); scanf ("% d", & search); mend = 0; fin = n - 1; milieu = (début + fin) / 2; while (beg <= end) {if (array [middle] end) printf ("La recherche a échoué!% d n'est pas présent dans la liste. \ n", recherche); getch (); } Différences clés entre la recherche linéaire et la recherche binaire
- La recherche linéaire est de nature itérative et utilise une approche séquentielle. D'autre part, la recherche binaire implémente l'approche diviser pour régner.
- La complexité temporelle de la recherche linéaire est O (N), tandis que la recherche binaire a O (log 2 N).
- Le meilleur temps dans la recherche linéaire concerne le premier élément, c’est-à-dire O (1). Par contre, en recherche binaire, c'est pour l'élément central, c'est-à-dire O (1).
- Dans la recherche linéaire, le cas le plus défavorable pour rechercher un élément est N nombre de comparaisons. En revanche, il s'agit du nombre log 2 N de comparaison pour la recherche binaire.
- La recherche linéaire peut être implémentée dans un tableau ainsi que dans une liste chaînée, tandis que la recherche binaire ne peut pas être implémentée directement dans une liste chaînée.
- Comme nous le savons, la recherche binaire nécessite le tableau trié, ce qui explique son traitement. Elle nécessite un traitement à insérer à l'endroit approprié pour conserver une liste triée. Au contraire, la recherche linéaire ne nécessite pas d'éléments triés, de sorte que les éléments sont facilement insérés à la fin de la liste.
- La recherche linéaire est facile à utiliser et aucun élément ordonné n'est nécessaire. D'autre part, l'algorithme de recherche binaire est toutefois délicat et les éléments sont nécessairement disposés dans l'ordre.
Conclusion
Les algorithmes de recherche linéaire et binaire peuvent être utiles en fonction de l'application. Lorsqu'un tableau correspond à la structure de données et que les éléments sont disposés dans un ordre de tri, la recherche binaire est préférable pour une recherche rapide . Si la liste chaînée est la structure de données, quelle que soit la manière dont les éléments sont organisés, la recherche linéaire est adoptée car la mise en œuvre directe de l'algorithme de recherche binaire n'est pas disponible.
L'algorithme de recherche binaire typique ne peut pas être utilisé dans une liste chaînée, car celle-ci est de nature dynamique et on ignore où l'élément central est effectivement attribué. Par conséquent, il est nécessaire de concevoir la variante de l'algorithme de recherche binaire qui peut également fonctionner sur une liste chaînée, car la recherche binaire est plus rapide à l'exécution qu'une recherche linéaire.
