Bi-partition

définition

La méthode de recherche binaire est un algorithme dont l'entrée est une liste ordonnée d'éléments.

Si l'élément recherché est contenu dans la liste, la recherche binaire renvoie sa position ; sinon il renvoie null.

Idée de base

1. Cette méthode est adaptée lorsque la quantité de données est importante.
2. Lors de l'utilisation de la recherche binaire, les données doivent être triées
3. En supposant que les données soient triées par ordre croissant, pour une clé de valeur donnée, démarrez la comparaison à partir de la position médiane de la séquence :
4. Si la valeur de arr[mid] à la position actuelle est égale à la clé, la recherche est réussie ;
5. Si la clé est inférieure à la valeur de position actuelle arr[mid], recherchez arr[low,mid-1] dans la première moitié de la séquence ;
6. Si la clé est supérieure à la valeur de position actuelle arr[mid], continuez à rechercher arr[mid+1,high] dans la seconde moitié de la séquence jusqu'à ce qu'elle soit trouvée.

complexité temporelle: