Le principe

La recherche binaire, ou recherche dichotomique, est une méthode efficace pour rechercher un élément dans une liste triée. Contrairement à une recherche linéaire, qui parcourt chaque élément un par un, la recherche binaire divise l’espace de recherche en deux à chaque étape, ce qui la rend beaucoup plus rapide dans les grandes listes.

Avant de pouvoir appliquer une recherche binaire, la liste doit être triée dans l’ordre croissant (ou décroissant, mais l’algorithme devra alors être adapté). En partant de cette hypothèse, on peut imaginer qu’on a une liste de nombres triés, par exemple [1, 3, 5, 7, 9, 11, 13, 15], et on cherche à savoir si le nombre 9 s’y trouve.

Le principe consiste à regarder l’élément du milieu de la liste. S’il s’agit de l’élément recherché, la recherche est terminée. Sinon, on compare cet élément à la cible. Si la cible est plus petite, on recommence la recherche sur la moitié gauche de la liste. Si elle est plus grande, on recommence sur la moitié droite. On répète ce processus jusqu’à trouver l’élément ou jusqu’à ce qu’il ne reste plus de sous-liste à explorer.

Le code

En Python, une implémentation simple de cet algorithme se fait de manière itérative. Voici un exemple :

def recherche_binaire(liste, cible):
    # Initialisation des bornes de début et de fin
    debut = 0
    fin = len(liste) - 1

    # Boucle tant que la zone de recherche est valide
    while debut <= fin:
        # Calcul de l'indice du milieu de la zone de recherche
        milieu = (debut + fin) // 2

        # Si l'élément au milieu est la cible, on retourne son indice
        if liste[milieu] == cible:
            return milieu

        # Si la cible est plus grande, on recherche dans la moitié droite
        elif liste[milieu] < cible:
            debut = milieu + 1

        # Sinon, on recherche dans la moitié gauche
        else:
            fin = milieu - 1

    # Si la cible n'est pas trouvée, on retourne -1
    return -1

Cette fonction retourne l’index de l’élément si celui-ci est présent dans la liste, sinon elle retourne -1.

Prenons un exemple d’utilisation :

nombres = [2, 4, 6, 8, 10, 12, 14, 16]
résultat = recherche_binaire(nombres, 10)
print(résultat)

Ce code affichera 4, car le nombre 10 se trouve à l’index 4 de la liste.

La méthode récursive

Il existe également une version récursive de la recherche binaire. Elle repose sur la même logique, mais au lieu d’utiliser une boucle, elle appelle la fonction elle-même avec une sous-section de la liste. Voici comment elle se présente :

def recherche_binaire_recursive(liste, cible, debut, fin):
    # Cas de base : si la zone de recherche est invalide, la cible n'est pas présente
    if debut > fin:
        return -1

    # Calcul de l'indice du milieu de la zone de recherche
    milieu = (debut + fin) // 2

    # Si l'élément au milieu est la cible, on retourne son indice
    if liste[milieu] == cible:
        return milieu

    # Si la cible est plus grande, on cherche dans la moitié droite (partie supérieure)
    elif liste[milieu] < cible:
        return recherche_binaire_recursive(liste, cible, milieu + 1, fin)

    # Sinon, on cherche dans la moitié gauche (partie inférieure)
    else:
        return recherche_binaire_recursive(liste, cible, debut, milieu - 1)

Et son utilisation :

nombres = [1, 3, 5, 7, 9, 11]
résultat = recherche_binaire_recursive(nombres, 7, 0, len(nombres) - 1)
print(résultat)

Ce code retournera 3, car le nombre 7 est à l’index 3.

L’avantage principal de la recherche binaire est sa complexité algorithmique en temps, qui est de O(log n). Cela signifie que même pour des listes très longues, le nombre d’itérations reste relativement faible. Par exemple, pour une liste de 1 000 000 d’éléments, il ne faudra qu’environ 20 vérifications pour déterminer la position de l’élément.

La recherche dichotomique

All work licensed under CC BY-NC-SA 4.0