Recherche dichotomique et tri par sélection
La recherche dichotomique est ton meilleur ami quand tu cherches quelque chose dans une liste triée. L'idée ? Tu regardes l'élément du milieu et tu élimines la moitié du tableau à chaque étape.
Le principe est simple : si l'élément du milieu est plus petit que ce que tu cherches, tu regardes à droite. S'il est plus grand, tu regardes à gauche. Tu continues jusqu'à trouver ta valeur ou épuiser les possibilités.
Complexité : O(log₂) - c'est hyper efficace ! Même avec un million d'éléments, tu n'auras besoin que de 20 étapes maximum.
💡 Astuce : La recherche dichotomique ne fonctionne QUE sur des tableaux déjà triés !
Pour le tri par sélection, on prouve sa correction avec un invariant de boucle : à chaque étape, la partie gauche du tableau est triée et contient les plus petites valeurs.
