Un tutoriel sur la recherche dichotomique.

Objectif.

Le but de ce tutoriel est de comprendre la recherche dichotomique.

Introduction.

  1. Essayons de programmer la fonction :
    int getPage(String pays) {
    .. / ..
    }
    qui renvoie le numéro de la page correspondant à un nom de pays donné, ou -1 si la page n'existe pas.

Travail proposé.

  1. Tester toutes les valeurs.

    Essayer le programme suivant :
    int getPage(String pays) {
        int debut = 0, fin = length();
        while(true) {
            int c = compare(pays, debut);
            if (c == 0) {
                return debut;
            } else{
                debut = debut +1;
            }
        }
    }
    avec un "main" en appelant getPage avec un nom de pays qui existe ("France").
    Noter que l'on utilise ici la construction return pour sortir de la boucle, tandis que while(true) est toujours vrai, donc boucle indéfiniment.
    • Quelle variable est utilisée et (provisoirement) inutile ici ?
    • Que se passe t'il si le pays existe ? Utiliser la fonction1 println() pour visualiser ce qui se passe à l'intérieur de la boucle.
    • Que se passe t'il si le pays n'existe pas ? Que manque t'il pour qu'il fonctionne comme nous l'espérions ?
    Notez que cet algorithme est bien long car il faut essayer toutes les valeurs.
  2. Couper le problème en deux : l'algorithme dichotomique.

    Voici une idée : On va couper l'espace de recherche en deux, puis en deux, puis en deux, etc. pour arriver à «cerner» la recherche, cela se formalise ainsi :
    • définir une intervalle {début, fin{ (la fin non incluse) où est la page recherchée
      • de valeur initiale {0, length(){length() est la taille du livre
    • puis de comparer la page recherchée avec la page du milieu de cette intervalle
      • et de réduire alors l'intervalle de moitié en remplaçant, selon, la borne de début ou de fin par le milieu
    • jusqu'à ce que l'intervalle :
      • soit de taille 1 : la page est alors trouvée
      • ou de taille 0 : la page n'existe pas
    A vous de traduire cet algorithme du langage courant en langage informatique, en partant du code précédent !
  3. Aller plus loin.

    Supposez que nous regardions l'annuaire téléphonique des 1048576 habitants des Alpes-Maritimes, triés par ordre alphabétique :
    • Expliquez en 2/3 lignes comment utiliser une méthode dichotomique pour chercher une personne parmi plus d'un million de personnes !
    • A l'aide de la suite des chiffres suivants, devinez en combien d'étapes la recherche dichotomique permet de trouver une personne parmi ce gros million :
      0, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576
      Note : cette liste de chiffres sont les puissances de 2: 2^0, 2^1, 2^2, etc...
    • A partir de la ligne de code :
      n = n + 1; u = u * 2; echo("2^" + n + "=" + u);
      écrire une boucle qui calcule les puissances de 2 de 0 à 20.

Remarques.

  1. La fonction void println(String string) affiche une chaîne de caractères sur la console.