Fiche de révision : Recherche dichotomique

📋 Plan du Cours

1. Principe de la recherche dichotomique
2. Déroulement sur une liste
3. Implémentation en Python
4. Terminaison et complexité
5. Comparaison avec la recherche linéaire
6. Conditions et usages pratiques

📖 1. Principe de la recherche dichotomique

🔑 Notions clés & Définitions

• Recherche dichotomique : Méthode de recherche qui fonctionne uniquement sur une liste triée et élimine environ la moitié des éléments à chaque étape.

📝 Points essentiels

• 🔄 La recherche dichotomique suit ces étapes:
  1. Examiner le milieu de la liste
  2. Comparer la valeur centrale à la valeur recherchée
  3. Conserver la moitié gauche si la valeur cherchée est plus petite
  4. Conserver la moitié droite si la valeur cherchée est plus grande
  5. Recommencer jusqu’à trouver la valeur ou épuiser l’intervalle

💡 Astuce mémo

Milieu → comparaison → moitié conservée → répétition

📖 2. Déroulement sur une liste

📝 Points essentiels

• Dans la liste [2, 3, 6, 7, 11, 14, 18, 19, 24], la recherche de 14 examine successivement 11, puis 18, puis 14, et trouve la valeur à l’indice 5.

💡 Astuce mémo

Une liste coupée en deux à chaque étape

📖 3. Implémentation en Python

★ À maîtriser

• La fonction Python trouve_dicho initialise les bornes indice_debut et indice_fin, calcule l’indice central avec une division entière, déplace une borne selon la comparaison avec val, retourne l’indice si la valeur est trouvée et retourne None sinon.

Compléments

• Pour la liste [2, 3, 6, 7, 11, 14, 18, 19, 24], trouve_dicho retourne 5 pour 14, 0 pour 2, 8 pour 24 et None pour 1976.

💡 Astuce mémo

valeur plus petite : gauche ; valeur plus grande : droite

📖 4. Terminaison et complexité

🔑 Notions clés & Définitions

• Variant de boucle : Quantité indice_fin - indice_debut qui diminue à chaque étape et garantit l’arrêt de l’algorithme.

★ À maîtriser

📌 La boucle while ne boucle pas à l’infini, car chaque itération retourne éventuellement un résultat ou réduit l’intervalle jusqu’à rendre fausse la condition indice_debut <= indice_fin.

📐 Formule — Dans le pire des cas, le nombre d’itérations vérifie $k = \log_2(n)$.

• La complexité temporelle de la recherche dichotomique dans le pire des cas est $O(\log_2 N)$.

Compléments

📐 Formule — Après k étapes, la taille du sous-tableau vaut $\frac{n}{2^k}$.

💡 Astuce mémo

L’intervalle diminue → la condition finit par devenir fausse

📖 5. Comparaison avec la recherche linéaire

★ À maîtriser

📌 La recherche par balayage linéaire a une complexité O(N), tandis que la recherche dichotomique a une complexité O(log₂ N).

• Quand la taille de la liste est multipliée par 10, le temps du balayage linéaire est multiplié par 10, tandis que celui de la recherche dichotomique est multiplié par environ 1,2.

Compléments

• Pour une liste de 100 000 valeurs, le balayage linéaire prend environ 4.43 ms, tandis que la recherche dichotomique prend environ 3.21 µs.

💡 Astuce mémo

Linéaire O(N) contre dichotomique O(log₂ N)

📖 6. Conditions et usages pratiques

★ À maîtriser

📌 La liste doit être triée avant d’utiliser la recherche dichotomique.

Compléments

📌 Pour effectuer plusieurs recherches, il est préférable de trier la liste une seule fois puis d’utiliser la recherche dichotomique, car le gain de temps devient considérable quand N est grand.

📊 Tableaux de synthèse

Balayage et dichotomie