Recherche dichotomique (binary search)
Définition
Définition (Wikipedia) : La recherche dichotomique, ou recherche par dichotomie (en anglais : binary search), est un algorithme de recherche pour trouver la position d’un élément dans un tableau trié. Le principe est le suivant : comparer l’élément avec la valeur de la case au milieu du tableau ; si les valeurs sont égales, la tâche est accomplie, sinon on recommence dans la moitié du tableau pertinente.
C’est la méthode qu’utilisais vos parents pour cherche un mot dans un dictionnaire.
C’est un algorithme de type diviser pour régner.
Exemple : Je cherche 42 dans le tableau suivant : [2 , 5, 12, 42, 47, 63, 72, 84, 149]
Algorithme:
L’algorithme en version itérative.
Exercice :
Preuve
Complexité
Implantation
Version récursive
Exercice
Mettre en oeuvre l'algorithme précédent en PythonSolution
code