Recherche dichotomique
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 la plupart des implémentations trouvées sur internet ne sont pas propres : elles mélangent des variantes incompatibles, utilisent des conditions aux bornes mal choisies, ou produisent des bugs subtils sur les cas limites. Ca vaut aussi sur wikipedia. C'est également la raison pour laquelle une IA vous donnera très probablement une version qui n'est pas propre : elle a été entraînée sur ce corpus de mauvaises implémentations. Restez sur la version présentée ici : elle est correcte par construction, grâce à la naturalité du recollement des intervalles semi-ouverts.
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.