TD No 3
from http://vernier.frederic.free.fr/Teaching/PimpA

Recherche par dichotomie et par interpolation

Questions sans code à écrire

1. Décrivez le principe général de la recherche par dichotomie.
2. Ecrivez l'algorithme de recherche par dichotomie en récursif et en itératif !
3. Ecrivez un algorithme hybride entre la recherche par dichotomie et la recherche par interpolation
   • si la valeur recherchée est > 2*(val_min+val_max)/3 prendre comme pivot 2*(index_min+index_max)/3
   • si la valeur recherchée est < 1*(val_min+val_max)/3 prendre comme pivot 1*(index_min+index_max)/3
   • sinon prendre le pivot par défaut (index_min+index_max)/2
4. Dans quel(s) cas est-ce que cet algorithme pourrait-être plus efficace ?
5. De nombreuses recherches par dichotomie sont-elles efficaces si il faut re-trier la liste avant chaque recherche ?

Implémentations

6. Codez le trie des communes par leur nom avec la méthode du trie rapide
7. Testez ! Pourquoi l'ordre change par rapport à la liste de départ ?
8. Codez une fonction de recherche par dichotomie des communes par leur nom
9. Testez, testez et re-testez!
10. Comptez le nombre d'essais et afficher le pour chaque recherche
11. Implémentez la recherche par interpolation sur la distance à Paris (avec une nouvelle fonction de trie !) qui retourne combien de communes il y a dans un cercle de rayon r
12. Rajoutez le code nécessaire pour retournez le nombre de français vivant dans ce rayon.
13. Est-ce possible sans rentrer dans un algorithe en O(n) à chaque nouvelle recherche autour d'une ville ?