Overview
La recherche binaire divise en deux un tableau trié jusqu’à trouver la cible ou épuiser l’intervalle.
Analogy
Comme chercher un mot dans un dictionnaire : ouvrir au milieu, décider gauche ou droite, recommencer.
Step-by-step
- low = 0, high = n-1.
- mid = (low + high) // 2.
- Si arr[mid] == cible → retour mid.
- Si cible < arr[mid] → high = mid - 1.
- Sinon low = mid + 1, tant que low <= high.
Visual
[1 3 5 7 9] → tester 5 → aller à droite → tester 7 → trouvé à l’index 3.
Common mistakes
- Oublier de recalculer mid après la mise à jour des bornes.
- Boucle avec < au lieu de <= qui saute le dernier élément.
- mid = (low+high) overflow dans certains langages (préférer low + (high-low)//2).
Practice questions
- Tracer l’algorithme sur 7 éléments avec cible aux extrémités et absente.
- Renvoyer l’index d’insertion si la cible est absente.
- Expliquer pourquoi le tableau doit être trié (contre‑exemple à l’appui).