Comment fonctionne l'algorithme de recherche binaire?

La recherche binaire fonctionne en analysant un tableau trié, en divisant successivement l'intervalle de recherche en deux.

1. Initialisation : Définir la limite gauche et droite de l'intervalle de recherche (habituellement le début et la fin du tableau).
2. Comparaison : Calculer l'indice du milieu de l'intervalle. La valeur à cet indice est comparée à l'élément recherché.
3. Réduction de l'intervalle :
   • Si la valeur du milieu correspond à celle recherchée, l'élément est trouvé.
   • Si la valeur du milieu est supérieure à celle recherchée, la recherche continue dans la moitié gauche de l'intervalle. La limite droite est déplacée à milieu - 1.
   • Si la valeur du milieu est inférieure à celle recherchée, la recherche continue dans la moitié droite de l'intervalle. La limite gauche est déplacée à milieu + 1.
4. Répétition : Les étapes 2 et 3 sont répétées jusqu'à ce que l'élément soit trouvé ou que l'intervalle de recherche devienne vide.

La complexité de l'algorithme est O(log n), ce qui est beaucoup plus efficace que la recherche linéaire pour de grands tableaux.

Exemple d'implémentation en Python :

def binary_search(arr, target):
    """
    Implémentation de la recherche binaire.
    Prend un tableau trié et la valeur recherchée.
    Retourne l'indice de l'élément ou -1 si non trouvé.
    """
    left, right = 0, len(arr) - 1

    while left <= right:
        mid = (left + right) // 2  # Calcul de l'indice du milieu
        mid_val = arr[mid]      # Obtention de la valeur au milieu

        if mid_val == target:
            return mid  # Élément trouvé
        elif mid_val < target:
            left = mid + 1  # La valeur recherchée est plus grande, recherche à droite
        else: # mid_val > target
            right = mid - 1 # La valeur recherchée est plus petite, recherche à gauche

    return -1 # Élément non trouvé