Introduction
Chercher efficacement une information dans une grande quantité de données est un défi fondamental en informatique. Lorsqu’un tableau est trié, il devient possible de trouver une valeur cible bien plus rapidement qu’en le parcourant intégralement. L’algorithme de recherche dichotomique, ou recherche binaire, exploite cet ordre pour diviser le problème à chaque étape. Il illustre parfaitement la capacité à décomposer un problème et à réutiliser une méthode algorithmique adaptée à une structure de données. Ce procédé est central pour de nombreuses applications concrètes comme la recherche dans un répertoire, le positionnement d’un élément dans une liste, ou l’accélération de la recherche dans des bases de données triées.
Comprendre le principe de la recherche dichotomique
Lorsqu’un tableau est trié, on peut chercher une valeur sans le parcourir de bout en bout. L’idée est de réduire l’intervalle de recherche par moitiés successives, jusqu’à isoler la valeur cible ou constater son absence.
Prenons l’exemple d’un tableau trié :
tableau = [3, 6, 9, 12, 15, 18, 21]
Si on cherche la valeur 15 :
On commence par comparer avec l’élément du milieu, ici 12.
Comme 15 > 12, la valeur cherchée ne peut être que dans la partie droite.
On recommence avec la moitié droite : [15, 18, 21].
Le milieu est 18. Cette fois, 15 < 18, donc on regarde la partie gauche de cette moitié : [15].
La valeur recherchée est trouvée.
Chaque étape divise l’espace de recherche. Cela permet de trouver une valeur en un nombre de comparaisons bien plus faible que dans une recherche classique.
À retenir
La recherche dichotomique fonctionne sur un tableau trié et divise l’intervalle de recherche à chaque étape pour localiser rapidement la valeur cible.
Implémentation et complexité de l’algorithme
Voici une implémentation en Python de la recherche dichotomique :
def recherche_dichotomique(tab, x):
gauche = 0
droite = len(tab) - 1
while gauche <= droite:
milieu = (gauche + droite) // 2
if tab[milieu] == x:
return milieu
elif tab[milieu] < x:
gauche = milieu + 1
else:
droite = milieu - 1
return -1
Cette version fonctionne uniquement si le tableau est trié par ordre croissant. Elle renvoie l’indice de la valeur trouvée ou -1 si elle est absente.
La recherche dichotomique divise l’intervalle à chaque itération. Si le tableau contient n éléments, le nombre maximal d’itérations est le plus petit entier k tel que 2ᵏ ≥ n, c’est-à-dire log₂(n). On dit que la complexité de l’algorithme est en O(log n). Cette notation exprime que le nombre d’opérations croît lentement même lorsque la taille du tableau augmente fortement.
À retenir
L’algorithme a une complexité logarithmique O(log n), car il divise la taille du problème par deux à chaque étape. Il est donc bien plus rapide qu’une recherche linéaire sur de grandes données.
Terminaison et correction : variant et invariant
Comme tout algorithme comportant une boucle, il est essentiel de s’assurer que la recherche dichotomique fonctionne toujours correctement et s’arrête toujours.
Terminaison : un variant de boucle
À chaque itération, la taille de l’intervalle [gauche, droite] diminue strictement. Plus précisément, droite - gauche forme un variant de boucle, c’est-à-dire une grandeur entière qui diminue à chaque passage et devient négative lorsque l’intervalle est vide. Cela garantit la fin de la boucle.
Correction : un invariant de boucle
L’invariant de boucle est la propriété suivante : si la valeur recherchée est présente dans le tableau, alors elle se trouve dans l’intervalle [gauche, droite] à chaque étape. La mise à jour des bornes (gauche ou droite) respecte cette propriété. Ainsi, si la valeur existe, on la trouvera nécessairement.
À retenir
La terminaison est assurée par un variant (l’intervalle de recherche diminue). La correction repose sur un invariant : la valeur cible reste toujours dans l’intervalle courant.
Comparaison avec la recherche linéaire
Pour mieux comprendre l’intérêt de la recherche dichotomique, comparons-la avec la méthode naïve : la recherche linéaire, qui examine chaque élément un par un.
def recherche_lineaire(tab, x):
for i in range(len(tab)):
if tab[i] == x:
return i
return -1
La recherche linéaire fonctionne quel que soit l’ordre du tableau, mais nécessite en moyenne n/2 comparaisons, et n dans le pire des cas. Sa complexité est O(n).
En comparaison, la recherche dichotomique est bien plus rapide : avec n = 1 000 000, elle fait au maximum log₂(1 000 000) ≈ 20 comparaisons, contre jusqu’à 1 000 000 pour la recherche linéaire.
À retenir
La recherche linéaire fonctionne toujours mais est lente. La recherche dichotomique est beaucoup plus rapide, à condition que le tableau soit trié.
Variantes, erreurs fréquentes et outils Python
Recherche dans un tableau décroissant
Si les éléments sont triés dans l’ordre décroissant, il faut inverser les comparaisons dans l’algorithme. Cela reste une recherche dichotomique, mais adaptée à l’ordre du tableau.
Risque de dépassement (avancé)
Dans certains langages de bas niveau, le calcul du milieu avec (gauche + droite) // 2 peut entraîner un dépassement de capacité si les indices sont très grands. Une version plus sûre utilise gauche + (droite - gauche) // 2. En Python, ce risque n’existe pas grâce à la gestion dynamique des entiers.
Cette subtilité est utile à connaître dans des contextes avancés, mais elle n’est pas exigée au niveau de Première.
Module bisect : automatiser la recherche
Le module bisect de Python permet d’utiliser directement une recherche dichotomique. La fonction bisect.bisect_left(tab, x) renvoie l’indice où x pourrait être inséré tout en conservant l’ordre du tableau. Cela permet de savoir où se situe x ou s’il est déjà présent.
import bisect
tab = [3, 6, 9, 12, 15, 18, 21]
indice = bisect.bisect_left(tab, 15)
if indice < len(tab) and tab[indice] == 15:
print("Trouvé à l’indice", indice)
else:
print("Non trouvé")
À retenir
Le module bisect propose une recherche dichotomique prête à l’emploi pour connaître l’indice d’insertion d’un élément dans une liste triée.
Conclusion
La recherche dichotomique illustre une stratégie algorithmique efficace, reposant sur la structure ordonnée des données et l’idée de diviser pour mieux chercher. Son coût logarithmique la rend incontournable dans le traitement rapide de données triées. Elle met en valeur des concepts essentiels de l’informatique comme l’invariant, le variant et la complexité algorithmique. Elle prépare aussi à des méthodes plus avancées comme la recherche dans des arbres équilibrés ou l’algorithme des k plus proches voisins, qui s’appuie sur la recherche d’éléments proches dans un espace structuré.