Introduction
L'algorithme de recherche dichotomique, également appelé recherche binaire, est un algorithme de recherche extrêmement efficace pour trouver un élément dans une liste triée. Il fonctionne en divisant la liste en deux parties égales et en comparant l'élément recherché à l'élément du milieu. En fonction du résultat de cette comparaison, il élimine la moitié de la liste et continue la recherche dans la partie restante.
Fonctionnement
La recherche binaire, ou recherche dichotomique, est un algorithme efficace utilisé pour trouver un élément spécifique dans une liste triée. Contrairement à la recherche séquentielle parcourant chaque élément un par un, la recherche binaire divise la liste en deux parties égales à chaque itération. L'algorithme compare l'élément recherché avec l'élément au centre de la liste. Si l'élément recherché est plus petit, la recherche continue dans la moitié inférieure de la liste, sinon elle se concentre sur la moitié supérieure. Ce processus se répète jusqu'à ce que l'élément soit trouvé ou que la taille de la sous-liste devienne nulle. Ce mécanisme permet de réduire de manière exponentielle le nombre de comparaisons nécessaires.
Le fonctionnement de la recherche binaire repose sur le fait que la liste doit être triée. Si la liste n'est pas triée, l'algorithme ne peut pas fonctionner correctement, car il se base sur l'hypothèse que les éléments sont ordonnés. À chaque étape, l'algorithme réduit la taille du problème de moitié, ce qui donne une complexité en temps de O(log n), où n est le nombre d'éléments dans la liste. Cette complexité logarithmique signifie que même pour des listes très grandes, le nombre de comparaisons reste relativement faible, ce qui rend l'algorithme beaucoup plus rapide que la recherche séquentielle.
L'algorithme commence par comparer l'élément recherché avec l'élément au centre de la liste. Si une correspondance est trouvée, la recherche s'arrête. Sinon, selon que l'élément recherché soit plus petit ou plus grand que l'élément central, la recherche se poursuit dans la moitié correspondante de la liste. À chaque itération, la taille de la sous-liste dans laquelle l'algorithme continue à chercher est réduite de moitié. Si la sous-liste devient vide, cela signifie que l'élément recherché n'existe pas dans la liste.
L'efficacité de la recherche binaire se vérifie particulièrement sur des listes longues, car la réduction de la taille de la recherche à chaque étape minimise le nombre de comparaisons. Cependant, l'inconvénient majeur de la recherche binaire est que la liste doit être triée à l'avance. Le processus de tri peut ajouter un coût supplémentaire, en fonction de l'algorithme de tri utilisé. Par exemple, un algorithme de tri rapide (comme QuickSort) peut être utilisé pour trier la liste en O(n log n) avant de procéder à la recherche binaire, mais ce processus peut être inutile si les données sont déjà triées.
En dépit de cette contrainte, la recherche binaire reste une des méthodes les plus efficaces pour rechercher un élément dans de grandes collections triées. Sa rapidité et sa faible complexité en temps la rendent largement utilisée dans de nombreux systèmes, comme les bases de données indexées, les systèmes de fichiers ou même les bibliothèques logicielles où l'efficacité de la recherche est primordiale. Cependant, pour des petites listes non triées ou des contextes où les données sont en constante évolution, la recherche séquentielle ou d'autres méthodes peuvent être préférées.
Voici les étapes de l'algorithme de recherche dichotomique :
- Initialisation : On commence avec deux indices, un pour le début et un pour la fin de la liste.
- Comparaison : L'élément du milieu de la liste est comparé à l'élément recherché.
- Réduction de la portée :
- Si l'élément recherché est plus petit que l'élément du milieu, la recherche se poursuit dans la moitié inférieure de la liste.
- Si l'élément recherché est plus grand, la recherche se poursuit dans la moitié supérieure.
- Réitération : On répète ce processus avec la moitié de la liste restante, jusqu'à ce que l'élément soit trouvé ou que la portée de recherche devienne vide.
Complexité
La recherche dichotomique a une complexité temporelle de O(log n), ce qui la rend beaucoup plus rapide que la recherche linéaire (O(n)) sur de grandes listes. Cependant, elle nécessite que les données soient déjà triées pour fonctionner correctement.
Applications
- Bases de données : Recherche rapide dans des ensembles triés.
- Systèmes de fichiers : Recherche de fichiers par nom dans des répertoires triés.
- Algorithmes de graphes et de recherche : Utilisé pour des optimisations dans les algorithmes de plus grands graphes ou réseaux.
Algorithme de recherche dichotomique
Voici l'algorithme d'un des types de recherches les plus rapides, soit la recherche dichotomique :
|
MODULE rechercheDichotomique(t[1...n],x) min ← 1 max ← n BOUCLE TANT QUE min ≤ max p ← (min + max) ÷ 2 SI t[p] = x ALORS RETOURNER p FIN SI SI t[p] ≤ x ALORS min ← p + 1 SINON t[p] >= x ALORS max ← p - 1 FIN SI FIN TANT QUE RETOURNER -1 |
Exemples
L'exemple suivant, écrit en Free Pascal, construire un tableau de suite de 50 nombres paires et retourne la position de certains nombres de ceux-ci en utilisant la recherche dichotomique :
- Program RechercheDichotomiqueSamples;
-
- Const
- n = 50;
-
- Type
- List50Integer=Array[1..n]of Integer;
- Var
- Tableau:List50Integer;
- I:Integer;
-
- Function rechercheDichotomique(Const t:List50Integer;x:Integer):Integer;
- Var
- _min,_max,p:Integer;
- Begin
- _min := 1;
- _max := n;
- While(_min <= _max)do Begin
- p := (_min + _max) shr 1;
- If t[p] = x Then Begin
- rechercheDichotomique := p;
- Exit;
- End;
- If t[p] < x Then _min := p + 1
- Else _max := p - 1;
- End;
- rechercheDichotomique := -1;
- End;
-
- BEGIN
- For I := 1 to 50 do Tableau[I] := I * 2;
- WriteLn('10=',rechercheDichotomique(Tableau,10));
- WriteLn('15=',rechercheDichotomique(Tableau,15));
- WriteLn('20=',rechercheDichotomique(Tableau,20));
- WriteLn('25=',rechercheDichotomique(Tableau,25));
- WriteLn('30=',rechercheDichotomique(Tableau,30));
- WriteLn('35=',rechercheDichotomique(Tableau,35));
- END.
on obtiendra le résultat suivant :
10=515=-1
20=10
25=-1
30=15
35=-1
L'exemple suivant, écrit en C, construire un tableau de suite de 50 nombres paires et retourne la position de certains nombres de ceux-ci en utilisant la recherche dichotomique :
- #define n 50
-
- int Tableau[n];
-
- int rechercheDichotomique(int t[],int x) {
- int _min,_max,p;
- _min = 1;
- _max = n;
- while(_min <= _max) {
- p = (_min + _max) >> 1;
- if(t[p] == x) return p;
- else if(t[p] < x) _min = p + 1;
- else _max = p - 1;
- }
- return -1;
- }
-
- int main(void) {
- for(int I = 1; I <= 50; I++) Tableau[I] = I * 2;
- printf("10=%i\n",rechercheDichotomique(Tableau,10));
- printf("15=%i\n",rechercheDichotomique(Tableau,15));
- printf("20=%i\n",rechercheDichotomique(Tableau,20));
- printf("25=%i\n",rechercheDichotomique(Tableau,25));
- printf("30=%i\n",rechercheDichotomique(Tableau,30));
- printf("35=%i\n",rechercheDichotomique(Tableau,35));
- return 0;
- }
on obtiendra le résultat suivant :
10=515=-1
20=10
25=-1
30=15
35=-1