Pourquoi la recherche dichotomique exige-t-elle un tableau trié ?
Réponse courte
Le tri permet de déduire, en comparant la cible à la valeur médiane, de quel côté elle peut se trouver. Sans ordre, une moitié ne peut pas être éliminée sans risque : la cible pourrait s’y cacher, même si le milieu est trop grand ou trop petit.
Comprendre
L’ordre justifie l’élimination
La recherche dichotomique compare la cible à la valeur au milieu de la zone examinée. Dans un tableau croissant, si cette valeur est inférieure à la cible, toutes les valeurs avant elle sont aussi trop petites. On peut éliminer le milieu et toute la partie gauche. Si elle est supérieure, le milieu et toute la partie droite sont trop grands ; on les élimine. À chaque étape, l’ordre donne une raison de réduire la zone.
Sans tri, le raisonnement s’effondre
Considère [2, 9, 1, 8, 3] et cherche 9. Le milieu est à l’indice 2 et contient 1, valeur inférieure à 9. Dans un tableau trié, on pourrait poursuivre seulement à droite ; ici 9 se trouve pourtant à l’indice 1, dans la partie gauche. Éliminer cette moitié ferait manquer la cible.
Ce que garantit la méthode
Le tableau [1, 2, 3, 8, 9] est trié : autour du milieu 3, une comparaison avec 9 permet de garder seulement la droite. La dichotomie est rapide parce que chaque comparaison élimine une partie des indices. Si les données ne sont pas triées, il faut d’abord les trier ou choisir un parcours qui n’utilise pas cette propriété. Une réponse juste par hasard sur un tableau désordonné ne démontre pas que la méthode y est correcte.
Exemples
- Dans [2, 9, 1, 8, 3], chercher 9 en comparant au milieu 1 puis en gardant seulement la droite échouerait : 9 est à gauche.
- Dans [1, 2, 3, 8, 9], la comparaison du milieu 3 avec 9 justifie de garder la partie droite.
- Si l’ordre d’un tableau n’est pas connu, parcourir toutes ses cases permet de vérifier l’absence sans éliminer une moitié à tort.
Pièges fréquents
- Croire qu’une comparaison au milieu suffit toujours à éliminer une moitié : cette conclusion exige l’ordre croissant ou décroissant annoncé.
- Confondre rapidité et validité : une recherche désordonnée peut parfois tomber sur la cible, mais n’offre pas de garantie de correction par dichotomie.
