Version en ligne

Tutoriel : Recherche dichotomique

Table des matières

Recherche dichotomique
Principe
Le recherche dichotomique en pratique

Recherche dichotomique

Principe

La recherche dichotomique est une manière efficace et rapide de rechercher un élément dans une structure de données triée (pour nous, ce sera un tableau trié).

En effet, jusqu'à maintenant vous aviez peut-être l'habitude de parcourir un tableau du début jusqu'à ce que l'on trouve la valeur, c'est-à-dire parfois jusqu'à la dernière case du tableau. Cette méthode est une recherche séquentielle, facile à écrire et à mettre en oeuvre certes, mais n'est efficace en terme de temps d'exécution que si le tableau parcouru est très petit.

Mais rassurez-vous, ce temps est révolu ! :p

Principe

Le recherche dichotomique en pratique

Voici une petite mise en situation, très simple.
Nous avons donc un tableau d'entiers trié.
Bien, maintenant imaginons que l'on demande à un utilisateur de saisir plusieurs nombres au clavier mais jamais le même, et que l'on stocke ces valeurs dans notre tableau. On doit donc, à chaque fois qu'il entre un nombre, vérifier que celui-ci n'est pas déjà dans le tableau.

Si l'on utilise la recherche séquentielle, on va chercher la valeur dans chaque case du tableau, en partant du début et ce jusqu'à ce qu'on la trouve (auquel cas on arrêtera la recherche). Voici un exemple assez simple de recherche séquentielle (donc, de ce qu'il ne faut plus faire ^^ ) sur lequel je ne vais pas m'éterniser car j'ai mis les explications nécessaires dans le code :

#include <iostream>
using namespace std;

int main()
{
  int val, nbVal;
  bool trouve, depasse;

  int tab[10] = {12, 14, 20, 25, 26, 28, 35, 99};  //tableau d'entiers trié par ordre croissant
  nbVal = 8;  //nombre de valeurs stockées dans le tableau
  
  cout << "Entrez la valeur que vous voulez rechercher dans le tableau." << endl;
  cin >> val;
  
  int i=0;
  trouve=false;
  depasse = false;

  while(i<nbVal && !(trouve || depasse)){  //on s'arrête si on trouve ou si on dépasse (car ordre croissant donc si on n'a pas trouvé avant, on ne trouvera pas après)
    trouve = (tab[i] == val);
    depasse = (tab[i] > val);
    i++;
  }
  
  if(trouve) cout << "La valeur est bien dans le tableau à l'indice : " << i << endl;
  else cout << "La valeur n'est pas dans le tableau" << endl;
  
  return 0;
}

Donc s'il y a 10 valeurs dans le tableau, ça va, ce n'est pas long ; mais dès qu'on en a plus, c'est autre chose ! En effet, si l'on a 10000 valeurs stockées et que celle que l'on recherche se trouve dans la 9999ème case, on va faire 9999 tours de boucle et donc 9999 comparaisons pour trouver cette valeur. Cela n'est donc pas un algorithme efficace puisque vous verrez que l'on va utiliser beaucoup moins de ressources processeur avec la recherche dichotomique.

Et alors, j'ai un ordinateur de guerrier, les 9999 comparaisons ne lui poseront pas problème, non ?

Oui, mais d'une part, vous ne développez généralement pas vos programmes que pour votre joli PC (pensez aux autres qui n'ont que le PC de leur grand-père ^^ ) et d'autre part, je répète ce que j'ai dit plus haut : la recherche dichotomique peut s'appliquer également sur des objets qui peuvent être beaucoup plus gros que des entiers (et là, les 9999 comparaisons, avec la recherche séquentielle, tu les sens passer, mon gars :p ).

Mais qu'a de différent une recherche dichotomique ?

Eh bien en fait, avec une recherche dichotomique, on ne va pas parcourir le tableau de façon linéaire, c'est-à-dire du début jusqu'à la fin. Plutôt que cette méthode, on va utiliser un critère de comparaison qui sera en adéquation avec le critère que l'on a utilisé pour trier le tableau.

L'idée ici est d'employer le fait que le tableau soit trié avec des valeurs classées par ordre croissant. Exemple :

int tab[10] = {12, 14, 20, 25, 26, 28, 35, 99};

On a ici un tableau rempli de "gauche à droite" par des entiers avec 12 qui est inférieur à 14 qui est lui-même inférieur à 20, etc.

L'idée est donc au départ (= au premier parcours de la boucle de recherche) de regarder au milieu du tableau.
Ainsi, là, on sait que l'on a 8 valeurs dans le tableau, il suffit de diviser ce nombre par 2 pour avoir l'indice du milieu : 4. Ici tab[4] correspond donc à la valeur 26. On compare donc tab[4] à la valeur recherchée.
Si celle-ci est supérieure à 26, on ne va rechercher notre valeur que dans la partie "supérieure" du tableau, c'est-à-dire les valeurs des cases qui ont des indices compris entre 4 et 8.
Et inversement, si celle-ci est inférieure à 26, on ne recherchera notre valeur que dans la partie "inférieure" du tableau, avec des indices compris entre 0 et 4.
Évidemment, si la valeur recherchée est dans la case dont on a obtenu l'indice(4), on arrêtera la recherche.

Là, j'ai simplifié un peu ! En fait, j'ai simplement "oublié" de vous dire qu'à chaque passage de boucle, on fait une petite opération pour réduire l'intervalle de recherche. On a en effet un indice de début et un indice de fin qui définissent un et un seul intervalle de recherche. On additionne ces deux indices et on divise le résultat par 2 pour obtenir l'indice du milieu de l'intervalle.

On se garde ainsi de comparer notre valeur à des moitiés de tableau à chaque passage de boucle. Un exemple est plus parlant je pense, et là, vous allez comprendre l'efficacité de la méthode : vous avez 1000 valeurs dans votre tableau. Si l'intervalle se réduit à chaque fois par deux, on a donc (on arrondit comme l'ordi ;) ) :
1000 / 2 = 500 ---> 1ère comparaison
500 / 2 = 250 ---> 2e comparaison
250 / 2 = 125 ---> etc.
125 / 2 = 63
63 / 2 = 32
32 / 2 = 16
16 / 2 = 8
8 / 2 = 4
4 / 2 = 2
2 / 2 = 1 ---> 10e comparaison

Eh oui, 10 comparaisons maximum, et en sachant qu'une comparaison = 1 tour de boucle, c'est beaucoup plus efficace que si on recherchait la valeur dans chaque case du tableau et où l'on devrait faire 1000 comparaisons et donc 1000 tours de boucle si la valeur était dans la dernière case.


Le recherche dichotomique en pratique

Le recherche dichotomique en pratique

Principe

Alors, en pratique, on ne fait rarement qu'une seule recherche dans un tableau. Il faut donc créer une fonction pour notre recherche dichotomique, et on l'appellera autant de fois que l'on a de recherches à faire.

C'est bien beau tout ça, mais que va renvoyer la fonction ?

En fait, elle va renvoyer l'indice où se trouve la valeur recherchée.

Et si la valeur n'est pas dans le tableau ?

T'es un petit malin, toi. :) Eh bien en fait, elle renverra une valeur spéciale, et pour ne pas compliquer la chose, on va admettre qu'elle renverra -1, puisque l'on suppose que toutes nos valeurs sont positives ou nulles.

La fonction de recherche dichotomique

Allez, c'est parti ! Voici le code de la fonction de recherche dichotomique :

/* fonction de recherche dichotomique qui renvoie un indice où se trouve la valeur "val" si elle est dans le tableau "tab[]" et -1 si cette valeur n'y est pas */
int rechercheDicho(int tab[], int nbVal, int val){

  /* déclaration des variables locales à la fonction */
  bool trouve;  //vaut faux tant que la valeur "val" n'aura pas été trouvée
  int id;  //indice de début
  int ifin;  //indice de fin
  int im;  //indice de "milieu"
  
  /* initialisation de ces variables avant la boucle de recherche */
  trouve = false;  //la valeur n'a pas encore été trouvée
  id = 0;  //intervalle de recherche compris entre 0...
  ifin = nbVal;  //...et nbVal
  
  /* boucle de recherche */
  while(!trouve && ((ifin - id) > 1)){

    im = (id + ifin)/2;  //on détermine l'indice de milieu
    
    trouve = (tab[im] == val);  //on regarde si la valeur recherchée est à cet indice
    
    if(tab[im] > val) ifin = im;  //si la valeur qui est à la case "im" est supérieure à la valeur recherchée, l'indice de fin "ifin" << devient >> l'indice de milieu, ainsi l'intervalle de recherche est restreint lors du prochain tour de boucle
    else id = im;  //sinon l'indice de début << devient >> l'indice de milieu et l'intervalle est de la même façon restreint
  }
  
  /* test conditionnant la valeur que la fonction va renvoyer */
  if(tab[id] == val) return(id);  //si on a trouvé la bonne valeur, on retourne l'indice
  else return(-1);  //sinon on retourne -1
  
}

J'ai mis directement des commentaires dans le code, je trouve que c'est plus compréhensible.

Juste pour la boucle : on boucle tant que l'on n'a pas trouvé la valeur recherchée et tant que ifin-id > 1, donc tant qu'il existe un intervalle.

Un main pour tester tout ça !

Je mets le code complet, avec le prototype de la fonction, le main et la fonction elle-même (oui, je sais que certains aiment les copier-coller ^^ ):

#include <iostream>
using namespace std;

int rechercheDicho(int [], int, int);  //prototype de la fonction de recherche dichotomique

int main()
{
  /* on déclare un tableau d'entiers que l'on initialise avec 8 entiers rangés par ordre croissant */
  int tab[10] = {12, 14, 20, 25, 26, 28, 35, 99};
  int nbVal = 8;  //nombre de valeurs stockées dans le tableau "tab[]"
  
  /* on demande la valeur que l'utilisateur veut rechercher dans le tableau */
  int val;  //variable stockant la valeur à rechercher dans le tableau
  cout << "Quelle valeur voulez-vous rechercher ?" << endl;
  cin >> val;
  
  /* on appelle la fonction de recherche dichotomique et on affiche le résultat  */
  int indiceRetourne = rechercheDicho(tab, nbVal, val);

  if(indiceRetourne != -1) cout << "Votre valeur est a l'indice : " << indiceRetourne << endl;
  else cout << "Votre valeur n'est pas dans le tableau." << endl;


  return 0;
}

/* fonction de recherche dichotomique qui renvoie un indice où se trouve la valeur "val" s'il est dans le tableau "tab[]" et -1 si cette valeur n'y est pas */
int rechercheDicho(int tab[], int nbVal, int val){

  /* déclaration des variables locales à la fonction */
  bool trouve;  //vaut faux tant que la valeur "val" n'aura pas été trouvée
  int id;  //indice de début
  int ifin;  //indice de fin
  int im;  //indice de "milieu"
  
  /* initialisation de ces variables avant la boucle de recherche */
  trouve = false;  //la valeur n'a pas encore été trouvée
  id = 0;  //intervalle de recherche compris entre 0...
  ifin = nbVal;  //...et nbVal
  
  /* boucle de recherche */
  while(!trouve && ((ifin - id) > 1)){

    im = (id + ifin)/2;  //on détermine l'indice de milieu
    
    trouve = (tab[im] == val);  //on regarde si la valeur recherchée est à cet indice
    
    if(tab[im] > val) ifin = im;  //si la valeur qui est à la case "im" est supérieure à la valeur recherchée, l'indice de fin "ifin" << devient >> l'indice de milieu, ainsi l'intervalle de recherche est restreint lors du prochain tour de boucle
    else id = im;  //sinon l'indice de début << devient >> l'indice de milieu et l'intervalle est de la même façon restreint
  }
  
  /* test conditionnant la valeur que la fonction va renvoyer */
  if(tab[id] == val) return(id);  //si on a trouvé la bonne valeur, on retourne l'indice
  else return(-1);  //sinon on retourne -1
  
}

Vous pouvez tester ce programme en rajoutant un :

cout << im << endl;

dans la boucle, et vous verrez évoluer l'indice du milieu à chaque tour de boucle. Cela permet de voir le nombre de tours de boucle et l'efficacité de l'algorithme. Ainsi pour la valeur 99, on obtient ce résultat :

Quelle valeur voulez-vous rechercher ?
99
4
6
7
Votre valeur est a l'indice : 7

Donc 3 tours de boucle, au lieu de 7 pour une recherche séquentielle. Et comme je vous l'ai expliqué plus haut, c'est encore plus efficace sur un grand nombre de valeurs (1000, 10000, 100000....). Vous n'avez qu'à tester le même algorithme avec un tableau de 1000 cases que vous aurez préalablement rempli avec une gentille boucle for, et vous verrez. :p Allez, à vous de jouer !

Voilà, vous savez maintenant ce que c'est qu'une recherche dichotomique !! Habituez-vous à faire ce type de recherche, beaucoup plus efficace qu'une recherche séquentielle (d'ailleurs, bannissez cette expression :pirate: ).


Principe