Algorithme de recherche dichotomique

Algorithme de recherche dichotomique : principes et mise en œuvre

La recherche dichotomique (ou recherche binaire) est une méthode efficace pour retrouver un élément x dans un tableau trié. En divisant à chaque itération l’intervalle de recherche en deux, elle atteint une complexité en temps O(log n), bien meilleure que la recherche linéaire O(n) lorsqu’on ne connaît pas la position de x. Ce cours détaille le fonctionnement de l’algorithme, les critères d’arrêt, les preuves de terminaison et les limites d’utilisation.

1. Structure de base de l’algorithme

Le pseudo‑code typique d’une recherche dichotomique itérative est le suivant :

deb ← 0
fin ← n‑1
tant que deb ≤ fin faire
    mil ← (deb + fin) // 2
    si t[mil] = x alors retourner mil
    sinon si x < t[mil] alors fin ← mil‑1
    sinon deb ← mil+1
fin
retourner -1  // x non trouvé

Les variables deb (début) et fin (fin) délimitent la partie du tableau encore à explorer. L’indice mil représente le milieu de cet intervalle.

2. Nombre maximal d’itérations

Dans le pire des cas, chaque itération réduit la taille de l’intervalle de recherche d’au moins un facteur deux. Ainsi, le nombre maximal d’itérations est donné par la fonction logarithme en base 2 :

• Formule : ⌊log₂ n⌋ + 1
• Exemple : pour n = 1024, log₂ 1024 = 10, donc la profondeur maximale est 10 itérations.

Cette borne est souvent exprimée comme ⌈log₂ n⌉, mais la version exacte ⌊log₂ n⌋ + 1 reflète le fait que la boucle s’arrête dès que l’intervalle devient vide.

3. Critères d’arrêt de la boucle « tant que »

La boucle s’interrompt dès que l’une des deux conditions suivantes est remplie :

• deb > fin : la zone de recherche n’existe plus, ce qui signifie que x n’est pas présent dans le tableau.
• t[mil] == x : l’élément recherché a été trouvé.

Ces deux cas sont résumés par le mnémonique « Dépasse ou Trouvé ». Toutes les autres propositions (par exemple fin‑deb = 0) ne constituent pas des critères d’arrêt définis par l’algorithme.

4. Mise à jour des bornes : le rôle du « variant de boucle »

Le variant de boucle est un concept de preuve de terminaison. Dans le contexte de la recherche dichotomique, le variant est la différence fin - deb. À chaque itération, cette différence diminue strictement :

• Si x est inférieur à t[mil], on met fin ← mil‑1, réduisant ainsi la partie droite de l’intervalle.
• Sinon, on met deb ← mil+1, réduisant la partie gauche.

Cette décroissance garantit que la boucle ne peut pas s’exécuter indéfiniment, assurant ainsi la terminaison de l’algorithme.

5. Exemple détaillé

Considérons le tableau t = [5, 7, 12, 14, 23, 27, 35, 40, 41, 45] et recherchons x = 9. La première valeur de mil est calculée comme suit :

• deb = 0, fin = 9
• mil = (0 + 9) // 2 = 4 (indice 4, valeur 23)

Comme x (9) est inférieur à 23, on met fin ← mil‑1 = 3. La prochaine itération donnera mil = 1, etc., jusqu’à ce que la condition d’arrêt soit atteinte.

6. Avantages comparatifs

Par rapport à la recherche linéaire, la recherche dichotomique présente deux avantages majeurs :

• Complexité en temps O(log n) contre O(n) pour la recherche linéaire.
• Moins d’accès mémoire grâce à la réduction rapide de l’intervalle de recherche.

Cependant, cet avantage ne s’applique que si le tableau est préalablement trié. Appliquer la recherche dichotomique à un tableau non trié rend le test t[mil] == x non fiable, car la position relative des éléments n’est plus garantie.

7. Limites et pièges fréquents

Lorsque l’on utilise la recherche dichotomique sur un tableau non trié, le principal problème est que le test d’égalité t[mil] == x ne permet plus de conclure correctement. En effet, le tableau ne respecte plus l’ordre croissant, et le choix du sous‑intervalle (gauche ou droite) devient arbitraire, pouvant conduire à des résultats erronés ou à une boucle infinie si le variant de boucle n’est pas correctement géré.

8. Questions fréquentes (FAQ)

9. Bonnes pratiques pour implémenter la recherche dichotomique

• Vérifier le tri du tableau avant d’appeler l’algorithme.
• Utiliser des int ou size_t pour les indices afin d’éviter les dépassements.
• Préférer la version itérative pour éviter le risque de débordement de pile en récursif.
• Inclure une gestion explicite du cas où x n’est pas présent (retourner -1 ou nullptr).

10. Conclusion

La recherche dichotomique est un pilier de l’algorithmique moderne grâce à sa rapidité et à sa simplicité d’implémentation. Maîtriser ses critères d’arrêt, son variant de boucle et ses conditions d’utilisation (tableau trié) permet de l’appliquer efficacement dans de nombreux contextes, du tri de bases de données aux algorithmes de recherche sur de grands ensembles de données.