Des élèves ont fabriqué un oeuf synthétique et veulent tester sa résistance à la chute : ils veulent savoir à partir de quel étage de leur lycée, l'oeuf se brise. Leur lycée compte 64 étages. On suppose que l'oeuf ne se casse pas si on le lance du rez-de-chaussée, mais qu'il se casse du dernier étage, et que l'on dispose d'autant d'oeufs que l'on veut.

1. Première méthode : on part du premier étage, on essaie, si l'oeuf n'est pas cassé, on monte au deuxième etc...
   Avec cette méthode combien fait-on d'essais dans le pire des cas ?
2. Deuxième méthode (méthode par dichotomie, qui vient du grec, et veut dire "couper en deux") : on essaie l'étage du milieu (le 32ème). Si l'oeuf résiste, on essaie l'étage au quart (le 16ème) sinon, on essaie l'étage au trois quarts (le 48ème), etc... Avec cette méthode combien fait-on d'essais dans le pire des cas ? Quel est le lien entre le résultat et 64 ?

Dans l'exemple introductif, le paramètre est le nombre d'étages, que nous noterons n.

• La complexité de la méthode 1 est n + 1. Cette complexité est linéaire.
• Soit p l'entier tel que 2 p-1 < n ≤ 2 p. La complexité de la méthode 2 est alors p + 1. Cette complexité est logarithmique.

L'algorithme de recherche dichotomique (ou recherche par dichotomie) algorithme s'applique dans le cas où on veut chercher si une valeur apparaît dans un tableau trié.

Le principe de l'algorithme est le suivant :

• Si le tableau est vide, on répond négativement.
• Sinon, on compare l'élément le plus centrale du tableau à la valeur recherchée. On distingue trois cas :
  • l'élément central est égal à la valeur : dans ce cas, on répond positivement.
  • l'élément est plus petit que la valeur : dans ce cas, si la valeur est dans le tableau, elle est nécessairement dans la deuxième moitié du tableau. On recommence l'algorithme sur cette moitié de tableau.
  • l'élément est plus grand que la valeur : dans ce cas, si la valeur est dans le tableau, elle est nécessairement dans la première moitié du tableau. On recommence l'algorithme sur cette moitié de tableau.

En pratique :

On suppose qu'on dispose d'un tableau trié représenté par la variable tab dans lequel on recherche une valeur val. Pour mette en oeuvre l'algorithme, on passe par deux variables, notées debut et fin et qui représentent l'indice de début et l'indice de fin de la partie du tableau dans lequel on recherche la valeur.

On procède alors de la façon suivante :

• Initialisation : debut = 0 et fin = len(tab) - 1.
• Tant que debut ≤ fin, on répète les instructions suivantes :
  • on calcule l'indice du milieu milieu = (debut + fin) // 2,
  • on compare tab[milieu] et val,
  • en cas d'égalité, on retourne True, sinon on met à jour la valeur des variables debut et fin :
    si tab[milieu] > val, alors debut reste inchangée, et fin devient égale à milieu - 1
    si tab[milieu] < val, alors fin reste inchangée, et debut devient égale à milieu + 1
• Si on sort de la boucle, on retourne False.

Remarque :

• À chaque itération, fin - debut décroît d'au moins une unité. Comme au départ on a fin - debut = len(tab) - 1, au bout d'au plus len(tab) itérations, fin - debut devient égal à -1, et la boucle se termine. On vient de prouver que l'algorithme se termine, ce que l'on appelle la terminaison de l'algorithme.
• À chaque itération, fin - debut est à peu près divisé par deux. La complexité de la recherche dichotomique dans un tableau trié est logarithmique.
• Cet algorithme est bien plus efficace que la recherche séquentielle vue précédemment. Mais il nécessite que le tableau soit trié. Or trier un tableau a un coût plus élevé que linéaire. Appliquer un algorithme de recherche dichotomique n'a donc d'intérêt que si on a affaire à un tableau déjà trié. Si le tableau n'est pas trié, appliquer une recherche séquentielle sera plus efficace que trier le tableau puis appliquer une recherche dichotomique.

À faire :

1. Programmer en Python une fonction recherche_dichotomique qui :
   • prend en paramètre un tableau tab trié dans l'ordre croissant et une valeur val,
   • recherche par dichotomie si val est dans tab, et retourne True si oui et False si non.

Par exemple :

recherche_dichotomique([], 3) doit retourner False
recherche_dichotomique([2, 4, 5, 6, 10, 20, 30], 3) doit retourner False
recherche_dichotomique([2, 3, 4, 5, 6, 10, 20, 30], 3) doit retourner True

2. Tester cette fonction avec plusieurs tableaux triés et plusieurs valeurs. Attention à tester le plus de cas possibles.
3. Programmer en Python une fonction est_trie qui :
   • prend en paramètre un tableau de nombres,
   • retourne True si ce tableau est trié dans l'ordre croissant et False sinon.
4. On veut faire en sorte que cette fonction s'arrête en affichant une erreur si le tableau passé en paramètre n'est pas trié. Pour cela, on va utiliser l'instruction assert qui est suivie d'un test et génère une erreur si le résultat de ce test est faux, et qui affiche alors un message.
   Ajouter en début de fonction (après la documentation) l'instruction suivante :
   assert est_trie(tab), "Le tableau en paramètre doit être trié !"
5. Tester cette nouvelle fonction avec un tableau trié, puis avec un tableau non trié.

Exécuter