Qu'est-ce qu'une recherche binaire?
Supposons qu'une personne possède un très grand assortiment d'articles et les range de manière ordonnée dans une longue rangée. Cette personne peut rapidement localiser un objet particulier dans la rangée en utilisant une recherche binaire. Cette recherche est effectuée en vérifiant l'élément du milieu dans la rangée et si l'objet du milieu n'est pas l'élément recherché, il ne cherche ensuite qu'une seule des moitiés de la rangée où pourrait se trouver l'élément. La personne saurait quelle moitié continuer à regarder car les éléments sont rangés dans l’ordre. Ces deux étapes sont répétées, sur des moitiés de plus en plus petites, jusqu'à ce que l'élément soit trouvé ou qu'il ne reste plus rien à regarder.
Dans le domaine de l’informatique, une recherche binaire est une procédure pas à pas qui permet de localiser l’emplacement ou l’index d’un élément dans un ensemble de données trié séquentiellement. Pour ce faire, il compare une valeur connue à un élément central désigné du tableau et, s’il n’est pas équivalent, contraint de manière répétée la comparaison des éléments centraux à la moitié pertinente la plus petite de l’ensemble jusqu’à ce qu’une équivalence soit atteinte ou que la liste soit épuisée.
Une recherche binaire, parfois appelée recherche à mi-intervalle, est beaucoup plus rapide qu'une recherche séquentielle de base qui commence à l'extrémité d'une liste d'éléments et compare chaque élément le long du chemin jusqu'à ce qu'une correspondance soit trouvée ou jusqu'à ce que la recherche atteigne la fin de la recherche. la liste. Si une personne avait 100 éléments consécutifs et que le dernier élément était celui recherché, une recherche séquentielle prendrait 100 comparaisons. Cependant, la méthode de bissection n’exige que sept comparaisons au maximum avant que l’élément ne soit trouvé. C'est évidemment beaucoup plus efficace qu'une recherche séquentielle.
L'inconvénient majeur d'une recherche binaire est que la liste des éléments doit être triée pour que cette recherche fonctionne. Trier une liste prend du temps. Trier puis utiliser ce type de recherche peut prendre plus de temps que de faire un autre type de recherche en premier lieu.
Pouvoir utiliser des informations, en particulier à partir de très grands ensembles de données, est important pour accomplir de nombreuses tâches de la vie. La discipline de l'informatique traite de nombreux types de problèmes, notamment la recherche de moyens efficaces de recherche d'informations afin d'obtenir des résultats utiles. Une recherche binaire n'est qu'un des nombreux algorithmes disponibles pour la recherche dans les données.