La recherche dichotomique

La recherche séquentielle

Comment implémenteriez-vous un algorithme de recherche dans une structure de données par exemple un tableau ? Le feriez-vous de la même manière si les données étaient triées ou prendriez-vous un petit temps de réflexion pour voir s'il existe meilleur ? Un débutant en programmation implémente intuitivement la recherche séquentielle, c'est cette même recherche que nous utilisons nous-même pour chercher une information dans une structure de données non-triée.

Imaginons un joueur de poker en pleine partie. La règle de base du texas hold'em, le poker le plus connu, est d'essayer de réaliser des combinaisons avec deux cartes en main et cinq cartes publiques. Le joueur cherche un carte dans le jeu, une carte qui lui permettrait d'obtenir un brelan, ce qui est une bonne main (trois cartes de même valeur), et lui permettrait avec un peu de chance de gagner le tour. Il a déjà deux cartes de même valeur dans sa main. Il ne lui reste plus qu'à trouver la troisième. Si le jeu n'est pas trié, il va forcément devoir utiliser la recherche séquentielle : il va comparer l'une après l'autre les cartes du jeu à une des deux cartes de la paire qu'il a déjà. Chez l'Homme, c'est automatique, le joueur n'y pense pas.



Le cerveau du joueur agit comme une fonction renvoyant un booléen : Il compare 4 à 8, ce n'est pas égal, donc il ne pourra pas faire de brelan avec cette carte (false). La même opération se réitère sur les cartes suivantes. Lorsqu'il compare 4 à 4, le cerveau du joueur constate que ces deux valeurs sont égales, il l'avertit alors que c'est bon, il tient son brelan (true). 4 comparaisons ont été nécessaires, ce nombre varie en fonction de l'emplacement de la carte recherchée et de manière générale de l'emplacement de l'élément recherché dans la structure de données. Ainsi, si dans un tableau de taille n en C++, la valeur recherchée est en bout de tableau, vous ferez n comparaisons tandis que si elle se trouve par exemple au milieu, vous en ferez n/2. Pour l'exemple du brelan, on aurait aussi pu imaginer que le joueur commence sur la droite auquel cas il y aurait eu deux comparaisons. On peut très facilement évaluer la complexité de la recherche séquentielle : avec la notation de landau, on conserve uniquement les opérations qui croissent vite comme les carrés mais ici, on simplifie le tout en disant qu'il y a n comparaisons, ce qui s'écrit alors O(n).

Le besoin d'un algorithme plus performant

Comme nous venons de le voir, la recherche séquentielle a une complexité simplifiée en O(n). Dans le pire des cas (carte recherchée en bout de jeu), la complexité est exactement en O(n) et dans le meilleur (carte recherchée en début de jeu), l'algorithme s'améliore en O(1). Mais il n'y a aucun moyen de prévisibilité. Si nous avons 100 cartes ? 10000 cartes ? 1000000 cartes ? Le nombre de comparaisons peut devenir très élevé ce qui ne fait qu'augmenter le temps d'exécution de la recherche surtout si cette même recherche doit être appliquée n fois (dans le cas d'un tri en O(n²) par exemple). L'Homme a trouvé la solution à ce problème : il utilise un nouvel algorithme de recherche : la recherche dichotomique. Je vais par la suite vous expliquer de quoi il s'agit exactement. Bien entendu, cela serait trop beau pour être vrai si l'algorithme en question fonctionnait toujours en ignorant l'état (trié, non-trié) de la structure de données concernée par la recherche. Pour qu'une recherche dichotomique puisse être effectuée, il faut que l'ensemble soit trié. S'il ne l'est pas, l'algorithme devient impossible d'utilisation, vous allez vite en connaitre la raison.

La recherche dichotomique

La recherche dichotomique est un algorithme plus rapide que la recherche séquentielle. Il consiste à diviser la structure de données en deux parties égales : une partie contenant forcément la valeur recherchée (si elle existe) et l'autre partie pouvant être ignorée. Pour cela, nous allons comparer l'élément recherché à la valeur médiane de la structure de données triée (pour cet exemple et pour les implémentations qui vont suivre, considérons les données triées par ordre croissant). Si la médiane est plus grande que la valeur recherchée, alors forcément cette dernière se situe entre le début de la structure et la médiane (elle exclue), par simple déduction. Rendez-vous bien compte du prodige que nous venons d'accomplir : en une comparaison, nous venons "d'éliminer" la moitié des valeurs, action qui aurait nécessité n/2 comparaisons avec la méthode séquentielle.

Ensuite, nous devons comparer la valeur recherchée à la médiane de la partie du tableau sélectionnée. Encore une fois, nous éliminons la moitié des valeurs de cette partie donc 1/4 de l'ensemble. Nous réitérons ce processus tant que la valeur recherchée n'est pas égale à la médiane comparée. Reprenons l'exemple du joueur de poker. Il a eu l'immense chance de tomber sur des cartes publiques triées. Il peut donc effectuer une recherche dichotomique pour trouver son 4. Je tiens encore à préciser que c'est intuitif et que nous utilisons réellement cet algorithme, même si nous n'y prêtons guère attention.



Le joueur regarde d'abord le 5 et s'aperçoit que ce nombre est plus grand que 4. Il sait donc que sa carte ne peut que se trouver entre 3 et 4. Il regarde la médiane de cette partie du jeu, 3, et en conclue que la carte recherchée, si elle existe, est celle entre 3 et 5. Si il sait qu'elle existe, il n'a même pas besoin de vérifier que c'est bien 4 : la carte se situe forcément à cet endroit. Deux comparaisons ont été nécessaire ou au pire trois. Maintenant imaginez qu'il aurait fallu chercher 3, ou 7 ou 8. Faites la démarche de l'algorithme de recherche dichotomique dans votre tête. Vous nécessiterez dans tous ces cas uniquement deux ou trois comparaisons. Le meilleur des cas serait survenu si nous cherchions la valeur qui se trouve être la médiane, 5 ; une comparaison aurait suffit.

Logarithmique - calcul de la complexité dichotomique

Comment évaluer la complexité de la recherche dichotomique ? Pour cinq éléments, on effectue en moyenne deux comparaisons, dans le meilleur des cas seulement une et dans le pire trois. La moyenne des comparaisons pour le même nombre d'éléments est donc de (1+2+2+3+3)/5 soit 2,2. Heureusement pour nous, des mathématiciens se sont penchés sur la question de la complexité dichotomique bien avant nous et ils ont trouvé que cette dernière se rapproche du logarithme en base 2 du nombre de données de la structure ; ce n'est pas pour rien que c'est en base 2, c'est parce qu'à chaque tour de boucle, on divise la partie de la structure sélectionnée par deux (on conserve successivement 1/2, 1/4, 1/8, 1/16, ... du total). Avec la notation de Landau, on écrit alors : O(log₂(n)).

Calculons cette valeur pour cinq éléments. Votre calculatrice ne vous permet pas directement de calculer des logarithmes en base 2 mais il existe une formule pour y parvenir à partir d'un autre logarithme : log_a(n) = log_b(n) / log_b(a). Cela signifit : "logarithme en base a de n est égal au logarithme en base b de n divisé par logarithme en base b de a". Une calculatrice ordinaire sait calculer les logarithmes en base e (≈ 2,718281828459) et en base 10. Les touches correspondantes sont respectivement nommées "ln" (logarithme népérien) et "log". Utilisons donc le logarithme le plus utilisé : log₁₀. Vous pouvez à présent calculer le logarithme en base 2 de 5 : log₂(5) = log₁₀(5) / log₁₀(2) ≈ 2,321928095. On trouve bien une valeur se situant entre 2 et 3, très proche de la moyenne calculée précédemment, 2,2 ! La fonction log₂ donne donc une approximation très intéressante de la complexité dichotomique.

Ici, nous allons parler du "caractère" récursif de la recherche dichotomique.

Rappel sur la récursivité

Histoire de vous remettre dans le bain, je vais brièvement vous rappeler en quoi consiste la récursivité. On parle de récursivité à partir du moment où une fonction s'appelle elle-même donc s'utilise elle-même. La mise en œuvre semble simple mais tout ce qui en découle est très intéressant à étudier et peut devenir très complexe. En résumé, la récursivité peut et/ou doit être utilisée quand un problème engendre un ou plusieurs sous-problème(s) semblable(s). Prenons pour exemple la fonction exponentielle - simplifiée pour l'utilisation de puissances entières uniquement - en base b : exp_b(n) = b*b*b ..... (n fois). Cette manière d'exprimer la fonction résulte d'un raisonnement itératif. Mais, considérons les équations suivantes qui sont vraies :

exp_b(n) = b*b*b ..... (n fois)
exp_b(n-1) = b*b*b ..... (n-1 fois)
exp_b(n) = b*exp_b(n-1)

La résolution de exp_b(n) pose forcément un nouveau problème semblable à ce dernier qui est exp_b(n-1). Par un simple raisonnement, on réussit à trouver, en pensant "récursivement", la troisième équation. La fonction doit renvoyer 1 une fois que n vaut 0, c'est ce qui définit la condition d'arrêt. Vue sous un certain angle, la fonction exponentielle s'utilise donc elle-même. Voilà pour l'exemple ; gardez bien cette idée de "problèmes et sous-problèmes identiques" en tête car c'est la raison d'être de la récursivité et nous allons retrouver une similarité dans l'algorithme de recherche dichotomique.

La recherche dichotomique : problème engendrant un sous-problème identique

À ce stade du cours, j'ose prétendre que vous avez bien assimilé l'algorithme de la recherche dichotomique. Si vous ne l'avez pas encore remarqué, la recherche dichotomique s'utilise elle-même. En effet, la toute première étape consiste à sélectionner une partie de la structure de données contenant forcément la valeur recherchée si elle existe. Ensuite, il s'agit de sélectionner la partie de la structure dans la sélection précédemment définie qui doit contenir la valeur recherchée si elle existe. Cela revient au même de dire qu'on applique à nouveau une recherche dichotomique sur la sélection définie précédemment par le même algorithme. Le problème initial est donc de choisir la bonne partie de la structure, mais cela étant fait, nous ne tenons toujours pas notre valeur cherchée (sauf si cette valeur est la médiane mais c'est un détail), un sous-problème identique naît alors.

En réalité, la récursivité est ici évidente, si évidente même qu'une implémentation itérative de la recherche dichotomique est plus difficile à mettre en œuvre qu'une implémentation récursive. Il y a des algorithmes qui sont récursifs de nature, comme si l'effort serait de les imaginer itératifs ; la recherche dichotomique ou les algorithmes "diviser pour régner" en règle générale sont les exemples les plus frappants. La récursivité est bien trop souvent vue comme un concept qui demande énormément de réflexion et qui est difficile à mettre en œuvre ; cette affirmation est fausse, tout dépend de l'algorithme. Vous aurez plus amplement l'occasion de le constater par vous-même dans les sous-parties suivantes.

Dans cette sous-partie nous allons analyser l'algorithme de recherche dichotomique implémenté de manière itérative (à l'aide d'instructions de boucle) et non de manière récursive. Nous allons construire la fonction au fur et à mesure de notre réflexion.
La première chose à faire est de créer le prototype de la fonction. Ce dernier différera du prototype de la fonction récursive. Alors, de quoi avons-nous besoin ? La structure de données que j'ai choisie est le vector (STL), nous devrons donc passer ce dernier en paramètre et de préférence par une référence pour ne pas en recréer un inutilement. Ensuite, nous devons indiquer à la fonction la valeur recherchée. La fonction renvoie l'emplacement de cette valeur dans le vector ou -1 si elle ne s'y trouve pas. On obtient alors ceci :
Code : C++ - Prototype
À quoi ressemblera exactement la fonction et comment fonctionnera-t-elle ? En réalité, nous allons définir la partie de la structure sélectionnée à chaque tour de boucle par deux variables, l'une marquant la première case de cette sélection et l'autre la dernière, ainsi, on "encadre" la partie intéressante. Nous allons aussi devoir utiliser la variable mediane qui nous permettra de choisir la bonne partie du tableau et à la fin de trouver la valeur recherchée. Voici donc les variables utilisées :
Code : C++ - Variables
Comme vous le remarquez sans doute, j'ai nommé le vector tab comme on a l'habitude de le voir. Comment continuer ? La boucle de l'algorithme sera un while qui tournera tant que deb <= fin . Dans ce while , nous aurons une structure if - else if - else if qui testera si la médiane du vector est égale, inférieure ou supérieure à la valeur recherchée. Si on trouve une égalité, on renvoie l'emplacement de la médiane, sinon on sélectionne une partie du vector et on calcule la nouvelle médiane :
Code : C++ - Boucle
Si deb est à un moment donné supérieur à fin , cela signifiera que la valeur recherchée ne se trouve pas dans le vector ; auquel cas on sort du while et on renvoie -1. En résumé, on obtient la fonction suivante :
Code : C++ - Récapitulatif
Ce que je vous conseille à présent, c'est de tester la fonction afin de constater l'efficacité de la recherche dichotomique ! Cette implémentation est itérative, vous pouvez donc l'implémenter dans un langage qui ne permet pas de récursions. À présent, nous allons nous intéresser à la version récursive de l'implémentation de la recherche dichotomique afin de pouvoir dresser un comparatif. C'est au programme de la prochaine sous-partie...

Comme vous vous y attendiez tous, ici nous allons implémenter la recherche dichotomique de manière récursive donc en ayant en tête que cet algorithme s'utilise lui-même. L'implémentation sera basé sur l'idée suivante :
Code : Autre - Paradigme
Le prototype de la fonction dichotomie sera différent de celui que nous venons de voir. En effet, nous devrons obligatoirement passer "l'encadrement" de la partie du vector sélectionnée en paramètre, c'est à dire l'indice de début et de fin de partie avec les variables debut et fin . Vous avez bien compris le principe alors, nous allons nous contenter d'appeler dichotomie en modifiant juste l'espace analysé et ceci tant que debut est supérieur ou égal (car sinon, il peut y avoir une erreur d'algorithmique) à fin et que (debut+fin)/2 (qui est la médiane) n'est pas égal à la valeur recherchée. Le prototype de la fonction peut donc ressembler à ceci :
Code : C++ - Prototype
La structure "globale" de la fonction sera un banal if - else :
Code : C++ - Structure globale
On aurait très bien pu inverser le code compliqué et le code simple, après vous faites comme vous le sentez. Dans mon exemple, le code simple, c'est le renvoi de la valeur -1 ; donc si l'algorithme entre dans le else , c'est que la valeur recherchée ne se trouve pas dans le vector. Au cas contraire, si l'algorithme entre dans le if , nous allons devoir effectuer une succession de trois conditions sous la forme if - else if - else if qui permettront de tester si la valeur recherchée est égale, plus grande ou plus petite que la médiane de la partie du vector sélectionnée. C'est aussi dans ce if que nous allons calculer cette médiane. S'en suit des testes conditionnels le renvoi de la bonne valeur (soit l'emplacement de la médiane, soit un des deux appels récursifs possibles) :
Code : C++ - Structure du code 'compliqué'
Je crois que nous avons fait le tour des explications, voici donc un récapitulatif de la fonction :
Code : C++ - Récapitulatif
Voilà, à présent, admirez la fonction récursive ! N'est-elle pas plus... logique ? Si je vous avais demandé d'implémenter vous-même la recherche dichotomique et ce de la manière qui vous semble la plus intuitive et la plus logique, c'est sans aucun doute cette implémentation que vous m'auriez présentée. bluestorm souligne une chose très importante dans son tutoriel sur la récursivité : Une personne ayant pour habitude de coder de manière itérative aura tendance à fuir la récursivité par peur de complication tandis qu'une personne codant la plupart du temps récursivement aura plus tendance à implémenter des algorithmes simples de manière très compliquée. C'est dans ces extrêmes qu'il ne faut pas tomber. Vous devez choisir la manière la plus logique - pour ne pas dire la plus automatique - pour vous pour coder tel ou tel algorithme. La recherche dichotomique est un algorithme que n'importe quel débutant "a envie" d'implémenter récursivement (c'était le cas pour moi et pour d'autres programmeurs amateurs ou pros que je connais) alors il faut le faire et surtout ne pas hésiter.

Profitons-en : Que se passe-t-il dans la pile d'appel ?

Profitons de l'occasion pour analyser la pile d'appel. Par contre, je ne vais pas définir cette notion, si vous ne savez pas de quoi il s'agit, lisez le tutoriel sur la récursivité dont j'ai donné le lien dans l'introduction. Pour cette analyse, je vais partir d'un exemple :
Code : C++
On déclare un vector d'entiers de 15 cases et on l'initialise à l'aide d'une boucle for avec des valeurs triées. À la fin de cette boucle, le vector contient les 15 valeurs suivantes :
Code : Autre
Nous allons réellement devoir suivre la pile d'appel lors du premier appel de dichotomie dans le main. L'analyse de la pile d'appel de fonctions se fait souvent sous la forme d'un texte indenté (afin de bien s'y repérer) en jouant à "l'interpréteur" C++. Ici, nous cherchons la valeur 5 dans l'intervalle 0 et tab.size()-1 , ce qui représente l'ensemble du vector. Voici donc "l'interpréteur" C++ :
Code : Autre - Interpréteur C++

Dernière optimisation : le polymorphisme paramétrique

Si vous ne l'avez pas encore remarqué, notre belle fonction dichotomie recherche bien par dichotomie mais elle ne s'adapte pas au type de données de la structure de données concernée par la recherche auquel elle a affaire. C'est un problème bien ennuyeux, cela signifie que quelqu'un qui ne s'y connait pas en programmation ne pourra que manipuler des entiers de type int, or l'optimum serait que l'on puisse utiliser la même fonction pour n'importe quel type ce qui impliquerait que c'est la fonction qui s'adapte au type et non pas l'inverse. Il faut que la fonction ait un comportement polymorphe, c'est à dire qu'elle puisse effectuer, en toute transparence, les mêmes opérations, qu'on lui envoie un vector d'int, de double ou de char. En C++, il existe pour cela une méthode simple et pratique qui est le template . Voici donc notre fonction récursive bien améliorée :
Code : C++ - fonction polymorphe
Note : Dans tous les codes que je vous ai donnés, j'utilise des else if et des else même si, dans certains cas, cela n'est pas nécessaire ; c'est juste pour vous montrer la "logique" du code.

La recherche dichotomique n'est que utilisable sur des données triées. Ici, vous allez avoir une première approche d'une astuce - et je dis bien une astuce, ne vous attendez donc pas à des miracles - pour appliquer une recherche dichotomique sur un ensemble concrètement non-trié. Attention, cette technique n'est avantageuse que si l'on tient à conserver l'ordre non-trié des valeurs de l'ensemble et si l'on souhaite souvent manipule cet ensemble (ajouts d'éléments, suppressions d'éléments, etc...).

Le principe est de créer une autre structure de données, de même taille que la structure concernée par la recherche, dans laquelle nous allons écrire, du début vers la fin et successivement, les emplacements des valeurs de la structure de données principale de telle sorte qu'en lisant cette structure dans un ordre précis et en allant se référer, à chaque lecture de valeur, à la structure principale, on retrouve les valeurs principales dans un ordre trié. Ce n'est pas si difficile à comprendre mais prenons un petit exemple : j'ai cette liste de valeurs sous la main :
Code : Autre
Je suppose qu'on est unanime pour dire que ces données ne sont pas triées. Réalisons donc la seconde liste (aussi appelée "table des pointeurs") telle que décrit précédemment : La plus petite valeur est 1 et elle se trouve à l'emplacement 4 de la liste, on commence donc par écrire dans la seconde liste :
Code : Autre
Successivement, nous allons chercher les autres valeurs et placer leur emplacement - dans la liste principale - dans la seconde liste. À la fin, nous nous retrouvons avec une seconde liste suivante :
Code : Autre
À présent, on lit, à partir des données de la seconde liste, la première liste :



Bref, il est possible d'effectuer une recherche dichotomique à partir de là, on renverra alors la valeur dans la seconde liste si la valeur recherchée est égale à la valeur "pointée" dans la liste principale par cette même valeur.

En quoi cette méthode peut-elle s'avérer utile ? Déjà, elle peut s'appliquer sur un ensemble non-trié en le triant indirectement. Nous ne pouvons pas la trier directement car nous partons du fait que l'on souhaite garder notre liste principale intacte, sinon il n'y a plus d'utilité à utiliser cette astuce. Ensuite, si vous ajouter un élément à la liste principale, il vous suffira d'insérer sa position dans la liste secondaire. C'est d'ailleurs pour cette raison que si vous voulez implémenter cet algorithme, je vous conseille d'utiliser les listes chaînées (en C++, voir std::list) et la dichotomie pour trouver l'emplacement où la valeur doit être insérée.

Le sujet est encore assez vaste, surtout si vous vous intéressez à la dichotomie dans son ensemble. Ce que je vous conseille donc, c'est d'aller encore plus loin en regardant d'autres diverses sources sur le net. Vous avez encore beaucoup à apprendre à ce sujet et je vous conseil vivement de le faire.

Quelques liens pratiques

• Site du zér0 \ Une classe d'algorithme non naïfs : Diviser pour régner
• Wikipédia \ Dichotomie
• ASP-PHP \ La recherche dichotomique
• ChronoMath \ Recherche dichotomique et logarithme népérien
• Wikituto \ Recherche dichotomique
• Algorithmes \ Algorithme de recherche dichotomique

Implémentation dans d'autres langages

Code : JavaScript

Code : PHP

Code : Java - Merci à quarante-sept pour ce code
Code : Autre - Ti-basic