Recherche dichotomique
Rappel d'ouverture (5 minutes, cours fermé)
On répond sans rouvrir les pages sur les tris.
- Pour chercher une valeur dans un tableau quelconque de \(n\) éléments, combien de comparaisons faut-il au pire ? Quelle complexité ?
- Qu'est-ce qui est vrai du début du tableau à chaque étape du tri par insertion ?
- Combien d'entiers contient l'intervalle semi-ouvert \([3 ; 7)\) ? Lesquels ?
Corrigé
- \(n\) comparaisons au pire (la valeur est en dernier, ou absente) : c'est du \(\mathcal{O}(n)\), linéaire. Il faut tout parcourir, faute de savoir où chercher.
- Le début du tableau est déjà trié ; on y insère l'élément suivant à sa place. C'est ce qui distingue ce tri de la sélection, où le début est trié et définitif.
- Quatre entiers : \(3, 4, 5, 6\). La borne de gauche est incluse, celle de droite exclue. Cette convention est celle de toute la page qui suit, et c'est elle qui rend l'algorithme juste du premier coup.
Le jeu du "plus ou moins"
Activité
La machine doit deviner un nombre entre 1 et 100 que vous avez choisi.
Quelle est la meilleure stratégie ?
- Proposer 1, puis 2, puis 3... → dans le pire des cas, 100 essais.
- Proposer 50 : si le nombre est plus grand, chercher entre 51 et 100 ; sinon entre 1 et 49. → l'intervalle est divisé par 2 à chaque essai !
Avec la stratégie "diviser par 2", combien d'essais au maximum pour trouver un nombre entre 1 et 100 ?
| Essai | Taille de l'intervalle restant |
|---|---|
| 0 | 100 |
| 1 | 50 |
| 2 | 25 |
| 3 | 13 |
| 4 | 7 |
| 5 | 4 |
| 6 | 2 |
| 7 | 1 → trouvé ! |
7 essais suffisent pour trouver parmi 100 nombres. C'est le principe de la recherche dichotomique.
Exercice 1 - Jouer au plus ou moins
Je pense à un nombre entre 1 et 16. Vous proposez toujours le milieu de l'intervalle courant.
Dérouler la stratégie si le nombre est 11.
Correction
| Essai | Proposition | Réponse | Nouvel intervalle |
|---|---|---|---|
| 1 | 8 | Plus grand | [9, 16] |
| 2 | 12 | Plus petit | [9, 11] |
| 3 | 10 | Plus grand | [11, 11] |
| 4 | 11 | Égal ! | Trouvé |
4 essais pour 16 nombres. On a bien \(\log_2(16) = 4\).
Application : chercher dans un tableau trié
Ne pas chercher d'autres versions en ligne
La recherche dichotomique est un algorithme classique, mais les implémentations que l'on trouve en ligne sont très hétérogènes : bornes incluses ou exclues, fin = milieu ou fin = milieu - 1, conditions d'arrêt différentes. Plusieurs de ces variantes sont correctes prises isolément, mais on ne peut pas en prendre un morceau et le recoller à une autre : c'est ainsi qu'apparaissent les bugs sur les cas limites (tableau vide, élément absent, dernier élément). Wikipédia n'y échappe pas, et une IA vous répondra elle aussi dans une convention qui n'est pas forcément celle du cours.
Restez donc sur la version présentée ici, en intervalles semi-ouverts [a ; b) : elle est correcte par construction, et surtout c'est la seule dont vous tenez l'invariant. Tant que vous ne savez pas énoncer l'invariant d'une variante, vous n'avez aucun moyen de dire si elle est juste : c'est précisément ce que ce chapitre vous apprend à faire.
Si un tableau est trié, on peut faire la même chose : comparer la valeur cherchée avec l'élément du milieu, et éliminer la moitié du tableau à chaque étape.
Entrée : un tableau trié T de taille n, une valeur val
Sortie : l'indice de val dans T, ou None si val est absente
1. gauche ← 0
2. droite ← n
3. Tant que gauche < droite :
4. milieu ← gauche + (droite - gauche) // 2
5. Si val < T[milieu] :
6. droite ← milieu
7. Sinon si T[milieu] < val :
8. gauche ← milieu + 1
9. Sinon :
10. Retourner milieu
11. Retourner None
Exemple tracé pas à pas
Tableau trié : [1, 3, 5, 7, 9, 11, 13], on cherche 7.
| Étape | gauche | droite | milieu | T[milieu] | Action |
|---|---|---|---|---|---|
| 1 | 0 | 7 | 3 | 7 | 7 == 7 → trouvé à l'indice 3 |
Autre exemple, on cherche 5 dans [1, 3, 5, 7, 9, 11, 13] :
| Étape | gauche | droite | milieu | T[milieu] | Action |
|---|---|---|---|---|---|
| 1 | 0 | 7 | 3 | 7 | 5 < 7 → droite = 3 |
| 2 | 0 | 3 | 1 | 3 | 5 > 3 → gauche = 2 |
| 3 | 2 | 3 | 2 | 5 | 5 == 5 → trouvé à l'indice 2 |
On peut se convaincre que ça marche : à chaque étape, si val est dans le tableau, elle est forcément dans la zone T[gauche..droite). On ne l'élimine jamais.
Exercice 2 - Valeur absente
Chercher 6 dans le tableau trié [1, 3, 5, 7, 9]. Tracer l'algorithme.
Que retourne-t-il ?
Correction
| Étape | gauche | droite | milieu | T[milieu] | Action |
|---|---|---|---|---|---|
| 1 | 0 | 5 | 2 | 5 | 6 > 5 → gauche = 3 |
| 2 | 3 | 5 | 4 | 9 | 6 < 9 → droite = 4 |
| 3 | 3 | 4 | 3 | 7 | 6 < 7 → droite = 3 |
| 4 | gauche = droite = 3 | — | — | — | gauche >= droite → sortie |
L'algorithme retourne None : 6 n'est pas dans le tableau.
Complexité : pourquoi c'est rapide
À chaque étape, on divise l'intervalle par 2. Pour un tableau de taille \(n\), le nombre d'étapes est au plus \(\log_2(n)\).
| Taille du tableau | Étapes max (dichotomie) | Étapes max (recherche naïve) |
|---|---|---|
| 100 | 7 | 100 |
| 1 000 | 10 | 1 000 |
| 1 000 000 | 20 | 1 000 000 |
La complexité est logarithmique : \(\mathcal{O}(\log n)\). C'est extrêmement rapide, même pour de très grands tableaux.
Condition indispensable
La recherche dichotomique ne fonctionne que sur un tableau trié. Sur un tableau non trié, elle peut rater des éléments pourtant présents.
Exercice 3 - Tracer la dichotomie
Tracer pas à pas la recherche de 11 dans [2, 4, 6, 8, 10, 11, 15, 20].
Combien d'étapes faut-il ?
Correction
| Étape | gauche | droite | milieu | T[milieu] | Action |
|---|---|---|---|---|---|
| 1 | 0 | 8 | 4 | 10 | 11 > 10 → gauche = 5 |
| 2 | 5 | 8 | 6 | 15 | 11 < 15 → droite = 6 |
| 3 | 5 | 6 | 5 | 11 | 11 == 11 → trouvé à l'indice 5 |
3 étapes pour un tableau de taille 8. On a bien \(\log_2(8) = 3\).
Exercice 4 - Comparer les approches
Pour un tableau de 1 024 éléments, combien d'étapes au maximum pour :
- Une recherche naïve (parcourir un par un) ?
- Une recherche dichotomique ?
Correction
- Recherche naïve : 1 024 étapes dans le pire des cas (l'élément est à la fin ou absent).
- Recherche dichotomique : 10 étapes, car \(\log_2(1024) = 10\).
La dichotomie est environ 100 fois plus rapide ici.