Le code de la recherche dichotomique

Voici une implémentation itérative (avec une boucle, sans récursion) de la recherche dichotomique. On initialise gauche à 0 et droite au dernier indice du tableau. Tant que gauche est inférieur ou égal à droite, il reste une zone à explorer.

def recherche_dichotomique(a, cible):
    gauche, droite = 0, len(a) - 1
    while gauche <= droite:
        milieu = (gauche + droite) // 2
        if a[milieu] == cible:
            return milieu
        elif a[milieu] < cible:
            gauche = milieu + 1
        else:
            droite = milieu - 1
    return -1

Détaillons les points sensibles. D'abord, la condition d'arrêt gauche <= droite (et pas <) : si on utilisait <, on manquerait le cas où l'intervalle contient exactement un élément (gauche == droite), ce qui ferait rater des valeurs présentes dans le tableau.

Ensuite, le calcul du milieu : (gauche + droite) // 2 fonctionne bien en Python, mais dans certains langages avec des entiers de taille limitée, gauche + droite peut provoquer un dépassement (« overflow ») si les indices sont énormes ; une version plus sûre est gauche + (droite - gauche) // 2, qui évite d'additionner deux grands nombres.

Enfin, la mise à jour des bornes doit toujours EXCLURE le milieu déjà testé : gauche = milieu + 1 et droite = milieu - 1, jamais gauche = milieu ou droite = milieu, sinon l'algorithme peut boucler indéfiniment en re-testant le même indice.

verification sur [1,3,5,7,9,11,13,15], cible=7 :
etape 1 : gauche=0, droite=7, milieu=3, a[3]=7  -> trouve a l'indice 3

Si la cible est absente (par exemple 8 dans ce tableau), la boucle se termine quand gauche dépasse droite, et la fonction renvoie -1.