Contenu

• Tableau de comparaison
• Définition de la recherche linéaire
• Définition de la recherche binaire
• Conclusion

La recherche linéaire et la recherche binaire sont les deux méthodes utilisées dans les tableaux pour recherche les éléments. La recherche est un processus de recherche d'un élément dans la liste des éléments stockés dans n'importe quel ordre ou de manière aléatoire.

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 que dans la recherche linéaire il n'y a pas une telle condition préalable. Bien que les deux méthodes de recherche utilisent des techniques différentes, décrites ci-dessous.

1. Tableau de comparaison
2. Définition
3. Différences Clés
4. Conclusion

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 connecter2N comparaisons
Peut être mis en œuvre sur	Tableau et liste chaînée	Ne peut pas être directement implémenté 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 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.

Programme C rechercher un élément avec la technique de recherche linéaire.

#comprendre #comprendre void main () {int a, n, i, item, loc = -1; clrscr (); f (" nEntrez le numéro d'élément:"); scanf ("% d", & n); f ("Entrez les nombres: n"); pour (i = 0; i <= n-1; i ++) {scanf ("% d", & a); } f (" nEntrez le numéro à rechercher:"); scanf ("% d", & item); pour (i = 0; i <= n-1; i ++) {if (élément == a) {loc = i; Pause; }} if (loc> = 0) {f (" n% d est trouvé à la position% d:", élément, loc + 1); } else {f (" 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 l'élément donné en comparaisons minimales possibles. 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:

1. Si l'élément est l'élément requis, la recherche est réussie.
2. Lorsque l'élément est inférieur à l'élément souhaité, recherchez uniquement la première moitié du tableau.
3. 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 maximum log (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.

Programme C trouver un élément avec une technique de recherche binaire.

#comprendre void main () {int i, début, fin, milieu, n, recherche, tableau; f ("Entrez le nombre d'élément n"); scanf ("% d", & n); f ("Entrez les% d nombres n", n); pour (i = 0; i <n; i ++) scanf ("% d", & array); f ("Entrez le numéro à rechercher n"); scanf ("% d", & search); mend = 0; fin = n - 1; milieu = (début + fin) / 2; while (beg <= end) {if (tableau <recherche) beg = middle + 1; else if (array == search) {f ("La recherche a réussi. n% d trouvé à l’emplacement% d. n", recherche, milieu + 1); Pause; } else end = middle - 1; milieu = (début + fin) / 2; } if (beg> end) f ("La recherche a échoué!% d n'est pas présent dans la liste. n", recherche); getch (); }

1. 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.
2. La complexité temporelle de la recherche linéaire est O (N), tandis que la recherche binaire a O (log₂N).
3. Le meilleur temps dans la recherche linéaire concerne le premier élément, à savoir O (1). Par contre, en recherche binaire, il s’agit de l’élément central, c’est-à-dire O (1).
4. Dans la recherche linéaire, le cas le plus défavorable à la recherche d'un élément est le nombre N de comparaison. En revanche, c'est log₂N numéro de comparaison pour la recherche binaire.
5. 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.
6. 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.
7. 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 cependant délicat et les éléments sont nécessairement rangé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 classés dans l'ordre, la recherche binaire est préférable rapiderecherche. 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 en raison de l'indisponibilité de la mise en œuvre directe de l'algorithme de recherche binaire.

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.