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.

tableau est une liste triée de longueur n
fonction recherche(tableau,x)
    i=0 et j=n-1
    tant que i<=j
si tableau[(i+j)//2]==x
retourner Vrai
sinon
si tableau[(i+j)//2]>x
                j=(i+j)//2-1
    sinon
         i=(i+j)//2+1
retourner Faux

Exercice :

Preuve

Complexité

Implantation

Version récursive