27. Binary Search (Recherche Binaire) : Exigence et Implémentation (O(log N))

La Binary Search est largement supérieure à la Linear Search, mais elle a une exigence stricte : les données doivent être triées.

Concept

La Binary Search élimine la moitié de l'espace de recherche restant à chaque étape. Elle fonctionne en vérifiant l'élément central de la plage actuelle.

1. Comparer la valeur cible avec l'élément central.
2. S'ils correspondent, retourner l'index central.
3. Si la cible est plus petite, passer à la moitié gauche.
4. Si la cible est plus grande, passer à la moitié droite.

Implémentation (Itérative)

python def binary_search(arr, target): low = 0 high = len(arr) - 1

while low <= high:
    mid = (low + high) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        low = mid + 1  # Search right half
    else:
        high = mid - 1 # Search left half
return -1

Efficacité : O(log N)