Recherche binaire

2.1 Définition de la recherche binaire et ses concepts de base

La recherche binaire est un algorithme de recherche d'un élément dans un tableau trié, qui fonctionne en divisant le tableau en deux moitiés. Cet algorithme est beaucoup plus efficace que la recherche linéaire pour les grands tableaux, car il réduit le nombre de vérifications en divisant le tableau en deux parties à chaque itération.

Concepts de base :

• Tableau trié : La recherche binaire fonctionne uniquement sur des tableaux triés.
• Division en deux : L'algorithme compare l'élément recherché avec l'élément au milieu du tableau.
• Division récursive ou itérative : Si l'élément recherché est plus petit que l'élément du milieu, la recherche continue dans la moitié gauche du tableau, sinon dans la moitié droite.
• Condition d'arrêt : La recherche s'arrête lorsque l'élément est trouvé ou que la plage de recherche devient vide.

Important ! Un tableau trié est nécessaire pour la recherche binaire.

Pour que la recherche binaire fonctionne correctement, les données d'entrée doivent être triées par ordre croissant. C'est la condition principale et unique, car l'algorithme repose sur le fait que les éléments du tableau sont ordonnés. Cela lui permet d'exclure efficacement la moitié des éléments à chaque étape de la recherche.

Exemple de tableau trié :

sorted_array = [1, 3, 5, 7, 9, 11, 13]

2.2 Implémentation étape par étape de la recherche binaire

Principe de fonctionnement de la recherche binaire :

1. Initialisation : Définir les limites initiales de la recherche (limites gauche et droite du tableau).
2. Choix de l'élément du milieu : Trouver l'indice de l'élément au milieu du tableau.
3. Comparaison : Comparer l'élément du milieu avec la valeur recherchée.
4. Mise à jour des limites :
   1. Si l'élément du milieu est égal à la valeur recherchée, retourner son indice.
   2. Si la valeur recherchée est inférieure à l'élément du milieu, mettre à jour la limite droite de la recherche.
   3. Si elle est plus grande, mettre à jour la limite gauche.
5. Répéter : Répéter les étapes 2-4 jusqu'à ce que l'élément soit trouvé ou que la limite gauche dépasse la droite.

Algorithme étape par étape :

1. Initialisation : Définir left à 0 et right à len(arr) - 1.
2. Calculer l'élément du milieu : mid = (left + right) // 2
3. Comparer à l'élément cible :
   1. Si arr[mid] == target, retourner mid
   2. Si arr[mid] < target, mettre à jour left = mid + 1
   3. Si arr[mid] > target, mettre à jour right = mid - 1
4. Répéter : Revenir à l'étape 2 tant que left <= right
5. Si l'élément n'est pas trouvé : Retourner -1

Implémentation itérative de la recherche binaire en Python :

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

# Exemple d'utilisation :
sorted_array = [1, 3, 5, 7, 9, 11, 13]
target = 7
result = binary_search(sorted_array, target)
print(f"Élément {target} trouvé à l'indice {result}")  # Sortie : Élément 7 trouvé à l'indice 3

2.3 Complexité temporelle de la recherche binaire O(log n)

La recherche binaire a une complexité temporelle de O(log n), où n est le nombre d'éléments dans le tableau. Cela signifie qu'à chaque étape, l'algorithme divise le nombre d'éléments en deux, ce qui accélère considérablement la recherche par rapport à la recherche linéaire, qui a une complexité temporelle de O(n).

Analyse de la complexité temporelle :

• Meilleur cas (Best case) : L'élément est trouvé dès la première étape, O(1).
• Cas moyen (Average case) : O(log n).
• Pire cas (Worst case) : L'élément est trouvé à la dernière étape ou absent, O(log n).

Exemple pour l'analyse de la complexité temporelle :

sorted_array = [1, 3, 5, 7, 9, 11, 13]
target = 7
index = binary_search(sorted_array, target)
print(f"Élément {target} trouvé à l'indice {index}")  # Sortie : Élément 7 trouvé à l'indice 3

# L'algorithme a effectué 3 étapes (logarithme de 7 éléments) pour trouver l'élément, 
# ce qui correspond à O(log n)

Représentation graphique de la complexité :

Imagine un tableau de 16 éléments.

Supposons que nous cherchons l'élément 15, alors les étapes seront les suivantes:

Première étape. Vérifier l'élément du milieu (8 éléments restent).

Deuxième étape. Vérifier l'élément du milieu dans la moitié restante (4 éléments restent).

Troisième étape. Vérifier l'élément du milieu dans la moitié restante (2 éléments restent).

Quatrième étape. Vérifier le dernier élément (1 élément reste).

En fin de compte, l'algorithme effectuera 4 étapes pour un tableau de 16 éléments, ce qui correspond au logarithme en base 2 de 16, c'est-à-dire, log2(16) = 4. C'est la complexité logarithmique O(log n).