Diviser pour régner

Le chapitre précédent a montré une récursivité qui réduit le problème d'un cran à chaque appel : une case de moins, un chiffre de moins, une unité d'exposant de moins. La réduction était réelle mais avare, et le nombre d'appels restait proportionnel à la taille des données. Il existe une autre façon de réduire, qui consiste à couper le problème en deux à chaque étape. Le nombre d'étapes s'effondre alors, et c'est cet effondrement qui fait la valeur de la méthode.

Deux recherches, deux comptes de pas

Soit un relevé de quarante-huit mesures rangées par ordre croissant, et la valeur 209 à retrouver. Elle se trouve en quarante-septième position, mais l'algorithme ne le sait pas. Voici d'abord la recherche apprise au chapitre sur les tableaux, qui examine les cases une par une.

Le compteur annonce 97 pas. C'est cohérent : quarante-sept tours de boucle à deux pas chacun, plus l'entrée et la sortie de la fonction. L'algorithme est correct et ne demande rien de particulier aux données.

Voici maintenant la même recherche, sur le même tableau et pour la même valeur, menée autrement. À chaque tour, l'algorithme examine la case du milieu de la zone encore possible. Si cette case porte la valeur cherchée, c'est fini. Sinon, la comparaison indique de quel côté continuer, et l'autre moitié est éliminée sans avoir été regardée.

Le compteur annonce 32 pas, pour la même réponse. Le rapport est de trois pour un, et il ne vient pas d'une écriture plus habile : il vient de ce que la boucle n'a tourné que cinq fois. La figure suivante rend ces cinq tours visibles en affichant chaque case examinée.

Les cases examinées sont les positions 24, 36, 42, 45 et 47. Cinq cases sur quarante-huit, et les quarante-trois autres n'ont jamais été lues. La différence entre les deux algorithmes est exactement là : non pas dans la vitesse d'un examen, mais dans le nombre d'examens nécessaires.

Pourquoi couper en deux change l'ordre de grandeur

La recherche linéaire élimine un candidat par examen. La dichotomie en élimine la moitié. La question intéressante est : combien de fois faut-il diviser par deux pour tomber à un seul candidat ?

La colonne de gauche est multipliée par mille d'une ligne à l'autre ; la colonne de droite gagne dix. Passer d'un million à un milliard d'enregistrements coûte dix examens de plus à la dichotomie, et neuf cent quatre-vingt-dix-neuf millions à la recherche linéaire. C'est ce genre d'écart qui décide si un traitement est faisable ou non, bien avant toute question de machine ou de langage.

La version récursive dit la même chose plus brièvement, et elle relie ce chapitre au précédent : le cas de base est la zone vide, le cas récursif est une moitié de la zone courante.

Le compteur descend à 26 pas, et la pile monte à six cadres. La hauteur de pile est ici tout à fait supportable, et pour une raison qui vaut d'être notée : elle vaut le nombre de divisions par deux, donc six pour quarante-huit mesures et trente pour un milliard. Une récursivité qui coupe en deux ne fait jamais déborder la pile, là où une récursivité qui retire une unité la fait déborder dès quelques dizaines de milliers d'éléments.

Le prix : un tableau déjà trié

Tout ce qui précède repose sur une hypothèse qui n'a jamais été discutée : le tableau est trié. Sans elle, la comparaison t[milieu] < cible ne dit rien sur le côté où continuer, et l'algorithme élimine une moitié au hasard.

Le tableau contient bien la valeur 99, en cinquième position. L'algorithme répond Position : 0, c'est-à-dire « absente », en 36 pas. Et il ne signale rien : il a fait son travail, tiré ses conclusions de comparaisons qui ne voulaient rien dire, et rendu une réponse fausse avec l'assurance d'une réponse juste.

Cette remarque déplace le problème plutôt qu'elle ne le résout. Si obtenir un tableau trié coûte plus cher que la recherche linéaire qu'on voulait éviter, l'affaire n'est pas rentable. Elle le devient dès que le même tableau est interrogé plusieurs fois : le tri se paie une fois, les recherches se paient par cinq examens. C'est exactement le raisonnement qui justifie un index dans une base de données. Et c'est la raison pour laquelle le chapitre suivant est consacré aux tris.

Tranche : extraire une portion de tableau

La dichotomie ci-dessus travaille sur des indices bas et haut et ne découpe jamais rien : c'est le procédé le plus économique, puisqu'il ne recopie aucune donnée. D'autres algorithmes du même genre ont besoin de vraies portions, manipulables comme des tableaux autonomes. Le tri fusion, au chapitre suivant, coupe le tableau en deux moitiés qu'il traite séparément avant de les réunir. Voici l'outil qui le permet.

Trois détails méritent une lecture attentive, car aucun n'est évident avec des indices qui commencent à 1.

La taille vaut b - a + 1, et non b - a. Les deux bornes sont comprises : la tranche de 3 à 7 contient les cases 3, 4, 5, 6 et 7, donc cinq cases. Le + 1 est la trace du fait que la borne de départ compte elle aussi. Oublier ce + 1 produit une tranche amputée de son dernier élément, et le défaut ne se voit pas tant que les tailles sont paires.

Le décalage d'indice s'écrit k - a + 1. La case lue est t[k], la case écrite est r[k - a + 1]. Quand k vaut a, l'expression donne 1 : le premier élément de la tranche va bien dans la première case du résultat. Quand k vaut b, elle donne b - a + 1, la dernière case. Écrire r[k - a] donnerait 0 au premier tour, et l'indice 0 provoque un arrêt immédiat, avec le message qui rappelle que le premier élément porte l'indice 1.

Une tranche est une copie, pas une vue. Tranche(t, 1, 3) fabrique un tableau neuf, rempli case par case. Modifier ce résultat ne modifie pas t, et c'est ce qui rend la fonction sûre à employer. En contrepartie, la copie a un coût proportionnel à la taille de la tranche, ce qui en interdit l'usage dans une boucle interne.

Le schéma général

La dichotomie est un cas particulier d'une manière de faire qui porte un nom.

La recherche dichotomique est un cas dégénéré du schéma : elle divise en deux, mais n'en traite qu'une seule moitié, et n'a donc rien à combiner. L'exemple suivant utilise les trois temps, avec Tranche pour le premier.

Le cas de base est un tableau d'une seule case, dont le maximum est son unique élément. Le cas récursif coupe en deux, demande le maximum de chaque moitié, et combine en gardant le plus grand des deux. Le déroulement prend 150 pas et empile cinq cadres, pour huit mesures que le parcours par boucle aurait traitées en bien moins.

Cette figure est donc un contre-exemple utile : ici, diviser pour régner coûte plus cher que la boucle, parce que chaque examen est précédé d'une copie, et que le nombre total d'examens ne diminue pas. Chercher un maximum oblige à regarder toutes les cases, quelle que soit la méthode. La dichotomie ne gagnait pas parce qu'elle coupait en deux, mais parce qu'elle jetait une moitié. C'est la distinction à retenir.

Vérification

Exercices type

Exercice 1 : écrire un algorithme qui devine un nombre compris entre 1 et 100 par dichotomie, en affichant chaque proposition et le nombre total de propositions nécessaires.

Exercice 2 : calculer la racine carrée entière d'un nombre, c'est-à-dire le plus grand entier dont le carré ne dépasse pas ce nombre, sans utiliser d'autre opération que la multiplication et la comparaison.

Exercice 3 : écrire la somme d'un tableau selon le schéma diviser pour régner, en employant Tranche, puis comparer son coût à celui de la boucle.

La méthode

1. Chercher ce qu'un examen permet d'éliminer, avant de choisir la méthode. Si un examen élimine un seul candidat, le parcours linéaire est la bonne réponse. S'il en élimine la moitié, la dichotomie s'impose.
2. Vérifier la propriété que la méthode exige, et l'écrire noir sur blanc : tableau trié, ou fonction croissante sur l'intervalle. Un algorithme dont l'hypothèse n'est pas garantie rend des réponses fausses sans se plaindre.
3. Poser les trois temps avant d'écrire : ce qui est divisé, ce qui est résolu récursivement, ce qui est combiné. Un temps absent est le signe d'un cas dégénéré, ce qui est permis mais doit être conscient.
4. Traiter le cas d'un seul élément comme cas de base, sans jamais tenter de découper une portion vide.
5. Exclure le point de coupe de la portion transmise, milieu + 1 ou milieu - 1. C'est ce qui garantit que la zone rétrécit strictement, donc que la boucle ou la récursion se termine.
6. Relever deux comptes de pas plutôt que d'argumenter : la méthode naïve et la méthode divisée, sur les mêmes données. L'écart, ou son absence, tranche la question.
7. Refuser le découpage quand il ne fait rien disparaître. Diviser des données pour ensuite tout examiner ajoute des copies et des appels à un travail inchangé.

Synthèse

• Sur le même relevé de quarante-huit mesures, la recherche linéaire coûte 97 pas et la dichotomie 32 : l'écart vient du nombre d'examens, quarante-sept contre cinq.
• Diviser par deux à chaque étape change l'ordre de grandeur du coût : multiplier les données par mille n'ajoute que dix examens.
• La recherche dichotomique s'écrit avec bas, haut et milieu ← (bas + haut) DIV 2, en excluant toujours la case examinée de la zone restante.
• La version récursive dit la même chose en moins de lignes, et sa pile ne dépasse jamais le nombre de divisions par deux, soit trente pour un milliard d'éléments.
• Tranche(t, a, b) extrait une copie de b - a + 1 cases, avec le décalage r[k - a + 1] ← t[k] qu'imposent des indices commençant à 1.
• Le prix de la dichotomie est un tableau déjà trié : sans cette garantie, la réponse est fausse et silencieuse.
• Diviser ne rapporte que si une portion est abandonnée sans lecture, ou si la combinaison coûte moins que le traitement direct.

Le prix vient d'être annoncé sans être payé : il reste à savoir comment trier, et ce que cela coûte. Les tris mettent trois méthodes sur les mêmes données et relèvent trois comptes de pas, dont l'une reprendra Tranche et le découpage en deux moitiés de ce chapitre.