Recherche dichotomique
Activité : Problème de dictionnaire
Dans un dictionnaire (le livre, par le type Python), les mots sont triés par ordre alphabétique.
Si vous deviez rechercher un mot dans le dictionnaire, utiliseriez-vous les algorithmes que nous avons vus jusqu'à présent ? Justifiez.
Un dictionnaire de langue française comporte, en général, plus de 40 000 mots. '
Pour le moment, les algorithmes que l'on a vus observent les éléments les uns après les autres, dans l'ordre croissant, jusqu'à trouver l'élément recherché, la fin de la liste ou encore un élément plus grand que l'élément recherché.
Donc si l'on cherche un mot comme zoo,qui a des chances de se trouver en fin de dictionnaire, en appliquant ces algorithmes il nous faudrait lire près de 40000 mots avant d'avoir une réponse, ce qui totalement déraisonnable.
Activité : vers un meilleur algorithme
Proposez une algorithme efficace pour rechercher un mot dans le dictionnaire. Traduisez-le en algorithme pour des cartes.
On l'a dit dans la solution de l'activité précédente : zoo a des chance de se trouver en fin de dictionnaire.
Dans une liste triée, on peut, en observant un élément, estimer si la valeur qu'on cherche doit se trouver avant où après.
Jouez à Devine un nombre entre 1 et 100 avec votre voisin.
On partage le dictionnaire en deux en l'ouvrant au milieu. TODO (prof) continuer ici