TP1 - Dichotomie

Objectifs

1. Comprendre le concept de l'algorithmique ;
2. Découvrir la dichotomie.

TP

L'ensemble du TP se fait sur python.

La dichotomie

Du grec dikhotomos, signifie "couper en deux".
En informatique, il s'agit d'une méthode coupant en deux une structure de données triée, pour gagner en temps d'exécution. Nous allons utiliser ce concept pour effectuer des recherches dans une liste, autrement appelée recherche dichotomique.
Cette recherche se veut bien plus rapide en temps d'exécution, qu'une recherche normale.

Principe de la dichotomie

La recherche dichotomique s'effectue toujours à partir d'une liste qui est triée. Son objectif est de retourner un booléen, suivant la présence d'un nombre à chercher dans la liste.
Voici les étapes de l'algorithme de la recherche :

• Je cherche l'élément dont l'indice correspond à la moitié de la liste ;
• Si cet élément est celui que je cherche, je retourne True ;
• Si l'élément cherché est plus grand que celui du milieu de la liste, cela signifie qu'il ne pourrait se trouver que dans la sous-liste "droite" de cette liste, on recommence donc l'opération à partir de la sous-liste droite ;
• Sinon, cela signifie que l'élément cherché est plus petit que celui du milieu de la liste, il faut donc faire la même chose avec la sous-liste "gauche" de cette liste.

En fonction des 2 options plus hautes, on parcourt à chaque itération de la boucle une liste 2 fois plus petite (si c'est plus grand, on regarde dans la partie droite de la liste, si c'est plus petit, on regarde dans la partie gauche).

Exercice de compréhension

On donne la liste suivante :

4	6	10	11	15	17	21	22

1. En utilisant le principe de recherche dichotomique, écrire (ou dessiner la liste) des étapes de recherche de l'élément 21.
2. Compter le nombre d'itérations qu'il aura fallu faire pour trouver la valeur.
3. Recommencer la recherche de l'élément 21 en itératif (on commence par la première valeur, puis la seconde, etc ...), et compter le nombre d'opérations qu'il aura fallu faire.
4. Déduire de la rapidité de la recherche dichotomique par rapport aux recherches "classiques".

Programmation

1. Écrire une méthode itérative recherche_iterative(liste, nombre) permettant de retourner l'indice du nombre cherché dans la liste s'il est présent, -1 sinon.
2. Écrire une méthode recherche_dicho(liste, nombre) implémentant l'algorithme de la recherche dichotomique.
3. Modifier ces 2 programmes pour qu'ils retournent un tuple comprenant en valeur True ou False, en fonction de si le nombre est trouvé dans la liste, ainsi qu'une valeur correspondant au nombre de tours de boucle pour trouver la valeur.