Qu'est-ce que la recherche binaire ?
What is binary search ?
Binary search is a search algorithm that finds the position of a target value in a sorted array. It eliminates the half in which the target value cannot lie. It searches the value in the other half. This continues by repeating the middle element to compare to the target value until the target value is found. 
Binary search is faster than linear search except for small arrays.
La recherche binaire est un algorithme de recherche qui permet de trouver la position d'une valeur cible dans un tableau trié. Il élimine la moitié dans laquelle la valeur cible ne peut pas se trouver. Il recherche la valeur dans l'autre moitié. La recherche se poursuit en répétant l'élément du milieu pour le comparer à la valeur cible jusqu'à ce que cette dernière soit trouvée.
La recherche binaire est plus rapide que la recherche linéaire, sauf pour les petits tableaux.
summarization
En informatique, la recherche binaire, également connue sous le nom de recherche par demi-intervalle, recherche logarithmique, ou encore de hachage binaire, est un algorithme de recherche qui permet de trouver la position d'une valeur cible dans un tableau trié. S'ils ne sont pas égaux, la moitié dans laquelle la cible ne peut pas se trouver est éliminée et la recherche se poursuit sur la moitié restante, en prenant à nouveau l'élément central pour le comparer à la valeur cible, et en répétant cette opération jusqu'à ce que la valeur cible soit trouvée. Si, à la fin de la recherche, la moitié restante est vide, la cible ne se trouve pas dans le tableau.

La recherche binaire s'effectue en temps logarithmique dans le pire des cas, ce qui donne

O(log n) comparaisons, où

n est le nombre d'éléments du tableau. La recherche binaire est plus rapide que la recherche linéaire, sauf pour les petits tableaux. Cependant, le tableau doit d'abord être trié pour appliquer la recherche binaire. Il existe des structures de données spécialisées conçues pour une recherche rapide, telles que les tables de hachage, qui peuvent faire l'objet d'une recherche plus efficace que la recherche binaire. Toutefois, la recherche binaire permet de résoudre un plus grand nombre de problèmes, tels que la recherche de l'élément le plus petit ou le plus grand suivant dans le tableau par rapport à la cible, même s'il est absent du tableau.

Il existe de nombreuses variantes de la recherche binaire. En particulier, la mise en cascade fractionnaire accélère la recherche binaire d'une même valeur dans plusieurs tableaux. La cascade fractionnaire permet de résoudre efficacement plusieurs problèmes de recherche en géométrie informatique et dans de nombreux autres domaines. La recherche exponentielle étend la recherche binaire aux listes non bornées. L'arbre de recherche binaire et les structures de données B-tree sont basés sur la recherche binaire.
fr