Comment fonctionne la recherche binaire et que nécessite-t-elle ?

Question

Accepted Answer

**Binary search** trouve une cible dans un tableau **trié** en réduisant répétitivement l'intervalle de recherche de moitié. Chaque comparaison élimine la moitié des éléments restants, donnant une complexité **O(log n)**. ## L'idée Regardez l'élément du milieu. S'il égale la cible, c'est terminé. Si la cible est plus petite, cherchez dans la moitié gauche ; si elle est plus grande, cherchez dans la moitié droite. Répétez jusqu'à ce que vous trouviez l'élément ou que l'intervalle soit vide. ## Exemple ```python def binary_search(arr, target): lo, hi = 0, len(arr) - 1 while lo <= hi: mid = (lo + hi) // 2 # middle index if arr[mid] == target: return mid # found it elif arr[mid] < target: lo = mid + 1 # discard left half else: hi = mid - 1 # discard right half return -1 # not present binary_search([1, 3, 5, 7, 9], 7) # -> 3 ``` ## Trace ```text Search 7 in [1,3,5,7,9] lo=0 hi=4 mid=2 -> 5 < 7 => lo=3 lo=3 hi=4 mid=3 -> 7 == 7 => return 3 ``` ## Complexité - **Temps :** O(log n). **Espace :** O(1) en itératif. ## Pièges **L'entrée doit être triée** — sinon les résultats sont dénués de sens. Attention aux erreurs de décalage dans `lo`/`hi` et au débordement d'entier dans certains langages (utilisez `lo + (hi-lo)//2`). ## Pourquoi c'est important Réduire de moitié l'espace de recherche transforme une recherche dans un million d'éléments en ~20 comparaisons. Le modèle diviser-pour-régner derrière lui réapparaît dans les arbres, les bases de données et d'innombrables problèmes d'entretien. Connaître son unique exigence stricte — une entrée triée — vous évite un bug classique et subtil.