Recherche linéaire contre recherche binaire
Contenu
- Contenu: Différence entre la recherche linéaire et la recherche binaire
- Tableau de comparaison
- Recherche binaire
- Différences Clés
- Conclusion
- Vidéo explicative
La différence entre une recherche linéaire et une recherche binaire est que, dans la recherche linéaire, chaque élément est vérifié et comparé, puis trié, tandis que dans la recherche binaire, une liste à trier est divisée en deux parties, puis triée. La recherche et le tri sont deux concepts principaux de la programmation informatique. De nombreux algorithmes sont utilisés pour la recherche et le tri, mais les deux algorithmes les plus utilisés pour la recherche et le tri sont la recherche linéaire et la recherche binaire.
La différence entre la recherche linéaire et une recherche binaire réside dans le fonctionnement et l'efficacité des deux algorithmes. La recherche binaire est un algorithme beaucoup plus efficace que l'algorithme de recherche linéaire. L'itération ou le temps nécessaire pour comparer chaque valeur avant le tri est moindre en recherche binaire par rapport à la recherche linéaire.
La recherche linéaire est un algorithme très complexe si vous souhaitez rechercher un nombre dans une liste, comparer et itérer parfois le nombre de valeurs de la liste. Un par un, chaque élément de la liste est récupéré et comparé à l'élément adjacent. Tous les éléments sont consultés et vérifiés, puis le bon élément est trouvé. Il peut y avoir pire cas si le dernier numéro de la liste est le numéro à rechercher. La recherche linéaire est la méthode par laquelle le tableau est parcouru et l'élément à rechercher est fondé. Si nous parlons d’efficacité, l’efficacité correspond au nombre de fois que le programme doit fonctionner pour trouver le nombre. Si nous trouvons le nombre que nous recherchons en première position, une seule comparaison doit être effectuée. Les choses sont triées. Sinon, les comparaisons doivent être répétées et la mémoire perdue. En moyenne, le nombre de comparaisons sera de (n + 1/2). Et l'efficacité la plus défavorable de cette technique est O (n) correspond à l'ordre d'exécution.
Comparée à la recherche linéaire, la recherche binaire est très efficace. Dans cette méthode, le tableau est divisé en deux parties, ce qui réduit considérablement le nombre de comparaisons par rapport à la recherche binaire. Le temps est également moins en recherche binaire par rapport à la recherche linéaire. La recherche binaire fonctionne de la manière dont l'élément central du tableau est trouvé, puis comparé à une partie du tableau. Il peut y avoir trois possibilités: le nombre du milieu peut être le nombre que nous devons trouver ou le nombre inférieur au nombre du milieu ou le nombre qui est supérieur au milieu du nombre du milieu. Le nombre de comparaisons est au plus log (N + 1). La recherche binaire par rapport à la recherche linéaire est un algorithme efficace par rapport à la recherche linéaire, mais le tableau doit être trié avant la recherche binaire.
Contenu: Différence entre la recherche linéaire et la recherche binaire
- Tableau de comparaison
- Recherche binaire
- Différences Clés
- Conclusion
- Vidéo explicative
Tableau de comparaison
| Base | Recherche linéaire | Recherche binaire |
| Sens | Recherche linéaire chaque élément est vérifié et comparé puis trié | Recherche binaire Une liste à trier est divisée en deux parties, puis triée.
|
| La complexité du temps | La complexité temporelle de la recherche linéaire est O (N). | La complexité temporelle de la recherche binaire est O (log 2 N) |
| Type d'algorithme | La recherche linéaire est itérative. | La recherche binaire est diviser pour régner. |
| Ligne de code | Dans une recherche linéaire, nous devons écrire plus de code. | Dans une recherche binaire, nous devons écrire moins de code. |
Recherche linéaire
La recherche linéaire est un algorithme très complexe si vous souhaitez rechercher un nombre dans une liste, comparer et parcourir plusieurs fois le nombre de valeurs de la liste. Un par un, chaque élément de la liste est récupéré et comparé à l'élément adjacent. Tous les éléments sont consultés et vérifiés, puis le bon élément est trouvé. Il peut y avoir pire cas si le dernier numéro de la liste est le numéro à rechercher. La recherche linéaire est la méthode par laquelle le tableau est parcouru et l'élément à rechercher est fondé. Si nous parlons d’efficacité, l’efficacité correspond au nombre de fois que le programme doit fonctionner pour trouver le nombre. Si nous trouvons le nombre que nous recherchons en première position, une seule comparaison doit être effectuée. Les choses sont triées. Sinon, les comparaisons doivent être répétées et la mémoire perdue. En moyenne, le nombre de comparaisons sera (n + 1/2). Et le pire cas d'efficacité de cette technique est O (n) correspond à l'ordre d'exécution.
Recherche binaire
Comparée à la recherche linéaire, la recherche binaire est très efficace. Dans cette méthode, le tableau est divisé en deux parties, ce qui réduit considérablement le nombre de comparaisons par rapport à la recherche binaire. Le temps est également moins en recherche binaire par rapport à la recherche linéaire. La recherche binaire fonctionne de la même manière que l'élément central du tableau, puis comparé à une partie du tableau.
Il peut y avoir trois possibilités: le nombre du milieu peut être le nombre que nous devons trouver ou le nombre inférieur au nombre du milieu ou le nombre qui est supérieur au milieu du nombre du milieu. Le nombre de comparaisons est au plus log (N + 1). La recherche binaire par rapport à la recherche linéaire est un algorithme efficace par rapport à la recherche linéaire, mais le tableau doit être trié avant la recherche binaire.
Différences Clés
- Recherche linéaire: chaque élément est vérifié et comparé, puis trié, tandis que la recherche binaire d'une liste à trier est divisée en deux parties, puis triée.
- La complexité temporelle de la recherche linéaire est 0 (N) alors que la complexité temporelle de la recherche binaire est O (log2N).
- La recherche linéaire est itérative alors que la recherche binaire est diviser pour régner.
- Dans la recherche linéaire, nous devons écrire plus de code, alors que dans la recherche binaire, nous devons écrire moins de code.
Conclusion
Dans cet article, nous voyons clairement la différence entre recherche linéaire et recherche binaire.
