En première

• Méthode dichotomique
• L'algorithme itératif
• Terminaison: le variant de boucle
• s'intéresser
• Exercices

Vous avez probablement joué au jeu 'trouve un nombre entre 1 et 100' et proposé 50. Si la réponse est 'perdu, c'est plus' vous proposez 75 et si l'on vous répond 'perdu c'est moins' vous proposez 62...C'est une recherche dichotomique!

Faire une recherche dichotomique, c'est chercher une valeur dans un tableau en prenant le milieu de l'ensemble des solutions possibles (qui sont donc rangées) pour éliminer la moitié des possibilités à chaque étape.

On utilise cette méthode pour résoudre f(x)=0 sur des fonctions strictement croissantes.

Voici l'algorithme itératif de la recherche dichotomique dans un tableau trié par ordre croissant. Itératif car on va utiliser une boucle. Il existe un algorithme récursif (fonction qui s'appelle elle même) que nous verrons en terminale.

	
➦ mettre debut à 0
➦ mettre fin à taille du tableau
➦ mettre trouve à Faux
➦ cherche est la valeur cherché
➦ tant que pas trouve et debut< fin
➦ 	index_milieu reçoit la partie entière de ()(debut+fin)/2)
➦ 	si liste[milieu] ==cherche
➦ 		trouve reçoit Vrai
➦ 	sinon
➦ 		si cherche>liste[milieu]
➦ 			debut reçoit milieu+1
➦ 		sinon
➦ 			fin reçoit milieu
➦ si trouve
➦ 	affiche milieu
➦ else
➦ 	affiche 'valeur non trouvée'
	

A vous de coder cela en python ou pourquoi pas en javascript dans une page html avec un formulaire qui demande la valeur min et max et longueur de liste. Puis qui construit et ordonne une liste de nombre. Le programme cherche ensuite une valeur aléatoire dans la liste et vous affiche les étapes (l'intervalle restant)

Puisque l'on a une boucle, on peut raisonnable s'interroger sur la terminaison de cet algorithme.

Dans le tant que, il y a la condition debut<=fin qui signifie que le tableau n'est pas vide. On va s'intéresser à la variable longueur=fin-debut qui est un entier. longueur est appelé un variant de boucle. Comme longueur décroit à chaque boucle, debut<=fin finira par être faux.

Pour prouver la terminaison d'une boucle on peut utiliser variant de boucle, cad un entier naturel qui décroit strictement à chaque itération.

Détaillons la preuve: on note E la fonction partie entière et on rappelle que E(x)<=x.

on note longueur_n la taille du tableau à l'étape n.

On passe à l'étape n+1:

• soit je trouve le nombre cherché, fin de l'algorithme
• soit fin=milieu-1. Alors
  longueur_n+1=fin_n+1-debut_n+1
  =E((fin_n+debut_n)/2)-1-debut_n≤ ((fin_n+debut_n)/2)-1-debut_n=longueur_n/2-1≤longueur_n-1< longueur_n.
  Donc longueur_n décroit dans ce cas.
• soit debut=milieu+1. Alors
  longueur_n+1=fin_n+1-debut_n+1
  =fin_n-(E((fin_n+debut_n)/2)+1)= fin_n-E((fin_n+debut_n)/2)-1.
  On utilise le fait que x-1< E(x) et donc -E(x)< 1-x. Du coup on a
  longueur_n+1 < fin_n +1 - (fin_n+debut_n)/2-1=longueur_n/2<=longueur_n.
  donc longueur_n décroit!
Si longueur_n est strictement décroissante et est un entier naturel, cette variable finira par valoir 0 et l'algorithme par s'arrêter.

La compléxité en log(n). Souvenez-vous du premier algorithme de recherche séquentiel en O(n)! C'est bien mieux en log(n).

La démonstration ci-dessous n'est pas au programme de 1ère

Soit un tableau de taille n, on note k le nombre d'opérations réalisées alors k est aussi le nombre d'itérations puisqu'il y a une opération par itération. La taille de l'intervalle de recherche est divisé par 2 à chaque itération, donc
à l'étape k, l'intervalle mesure E(n/2^k) et,
comme l'intervalle le plus petit a une longueur de 1, 1≤E(n/2^k)≤n/2^k.
Si on multiplie par 2^k on a: 2^k≤n.
En passant au logarithme décimal, on obtient: klog(2)≤log(n) donc k≤log(n)/log(2)=log₂(n).

1. Coder la recherche dichotomique dans un tableau ordonné.
2. Coder la recherche du zéro d'une fonction continue, monotone sur un intervalle donné.