Recherche dichotomique
Trouve une valeur dans un tableau trié en regardant au milieu et en écartant la moitié où elle ne peut pas être. Chaque comparaison divise le reste par deux.
- meilleur cas Ω(1)
- cas moyen Θ(log n)
- pire cas O(log n)
- espace O(1)
Que veulent dire ces termes ?
- Trié : rangé par ordre croissant. La recherche dichotomique en a besoin ; sur des données non triées, elle se trompe.
- Diviser par deux : chaque comparaison écarte la moitié du reste, celle où la cible ne peut pas être.
- log₂ n : combien de fois on peut couper n en deux avant d’arriver à 1. Pour 64 valeurs, 6, donc 7 comparaisons au plus.
- milieu (mid)
- trouvée
- écartée
- cible
Chaque milieu que la recherche pourrait choisir ; une exécution est un chemin vers le bas. Niveaux : 5 = ⌈log₂(24 + 1)⌉, le maximum de comparaisons nécessaires.
On cherche 70 parmi 24 valeurs triées : tout le tableau est encore en jeu.
Espace : lecture ou pause. Flèches gauche et droite : pas à pas. Origine et Fin : sauter.
Essayez : Choisissez une cible absente du tableau. La recherche s’arrête quand même après au plus ⌈log₂(n + 1)⌉ comparaisons, quand lo dépasse hi.
Comment ça marche
La recherche dichotomique garde deux repères, lo et hi, autour de la partie du tableau où la cible peut encore être. Elle regarde la valeur du milieu : si c’est la cible, c’est fini ; si elle est plus petite, la cible ne peut être qu’à droite, donc lo passe après le milieu ; si elle est plus grande, hi passe avant. Chaque étape coupe le reste en deux : 64 valeurs demandent au plus 7 comparaisons, un million au plus 20. Quand lo dépasse hi, il ne reste rien : la valeur n’est pas dans le tableau.
Quand le choisir
Utilisez la recherche dichotomique dès que les données sont triées et que l’on peut sauter à n’importe quelle position : un mot dans une liste triée, une version dans un historique, git bisect, l’endroit où insérer dans un tableau trié. Sur des données non triées, elle se trompe, et trier d’abord ne vaut le coup que pour de nombreuses recherches.