Des volumes importants de données sont susceptible d’être traitées par les ordinateurs. Des algorithmes efficaces sont alors nécessaires pour réaliser ces opérations comme, par exemple, la sélection et la récupération des données.Les algorithmes de recherche entrent dans cette catégorie.Leur rôle est de déterminer si une donnée est présente et, le cas échéant, d’en indiquer sa position, pour effectuer des traitements annexes. La recherche d’une information dans un annuaire illustre cette idée. On cherche si telle personne est présente dans l’annuaire afin d’en déterminer l’adresse. Plus généralement,c’est l’un des mécanismes principaux des bases de données :à l’aide d’un identifiant, on souhaite retrouver les informations correspondantes.
Dans cette famille d’algorithmes, la recherche dichotomique permet de traiter efficacement des données représentées dans un tableau de façon ordonnée.
Une première façon de rechercher une valeur dans un tableau est d’effectuer une recherche naïve à l’aide d’un parcours de tableau, que l’on peut programmer ainsi:
def recherche_naive(val, tab):
for i in range(len(tab)):
if tab[i] == val:
return True
return FalseIci, on renvoie True en cas de succés et False en cas d’échec.
Comme tout algorithme ayant cette forme, la complexité est linéaire, c'est à dire proportionnelle à la longueur du tableau, donc le temps de recherche double lorsque la longueur du tableau double. Mais avec cette méthode, on n’exploite pas le caractère ordonné du tableau, ce qui fait savoir que telle valeur du tableau n’est pas la valeur recherchée n’apprend absolument rien sur les autres valeurs du tableau.
Le concept de cette approche repose sur l’idée de réduire de moitié l’espace de recherche à chaque étape. On dispose d'un tableau t trié de valeurs, et on cherche à déterminer si une valeur v est présente dans le tableau.
Pour cela, on procède avec l'algorithme suivant :
Tant que le tableau n'est pas vide FAIRE
On regarde l'élément du milieu du tableau et on le compare à v.
S'ils sont égaux, Afficher "v est dans t" et FIN de l'algorithme,
sinon si, l'élément du milieu est supérieur à v, on poursuit la recherche dans la moitié inférieure du tableau.
sinon, on poursuit la recherche dans la moitié supérieure du tableau.
Fin Tant que
Afficher "v n'est pas présent dans t".
Testons cela avec le simulateur suivant :
Vous pouvez générer une suite et choisir un nombre, puis lancer une recherche.
[1,2,3,4,4,5,6,7,7,8,9,10,11,20,23,24,26,30,46,67,68,69,72,73,74,74,75,78]Choisir un nombre :
Pour étudier la complexité d'un algorithme il faut envisager la pire des situations. Considérons que nous devons chercher un élément dans un tableau de N éléments. La pire situation est que l'élément recherché ne figure pas dans le tableau.
Dans le cas de l'approche naïve il y aura donc N boucles, pour une compléxité linéaire.
Voici le code correspondant à l'algorithme de l'approche dichotomoque :
def recherche_dicho_liste(val, tab):
while len(tab) > 0:
c=(len(tab)-1)//2
if tab[c] == val:
return True
elif tab[c] > val:
tab = [tab[i] for i in range(c)]
else:
tab = [tab[i] for i in range(c+1,len(tab))]
return False
Soit k le nombre de boucles, on comprend facilement que k est le plus petit entier vérifiant 2k > N.
Voici un tableau donnant des valeurs de k en fonction de N :
| N nombre d'élément dans le tableau | k nombre de boucles |
|---|---|
| 100 | 7 |
| 1000 | 10 |
| 1000000 | 20 |
| 1000000000 | 30 |
Ce type de croissance ultra-lente est appelée croissance logarithmique. Notre algorithme a un nombre de boucle très intéressant mais en utilisant des tableaux dans chaque boucle qui pour être créer nécessite un nombre d'instruction proportionnelle à N (N/2, N/4 etc...). Donc ce qui a été gagné avec le nombre de boucles est perdu avec l'utilisation des tableaux.
C'est pourquoi nous allons utiliser les index du début et de la fin de la zone de recherche dans le tableau.
Voici à quoi va ressembler le nouvel algorithme :
index_debut ⟵ 0 index_fin ⟵ (longueur du tableau) - 1 Tant que (index_fin - index_debut) >= 0 FAIRE c ⟵ (index_debut + index_fin) // 2 Si c = v, alors, Afficher "v est dans t" et FIN de l'algorithme, sinon si c < v, alors, index_debut ⟵ c+1 sinon, index_fin ⟵ c-1 Fin Tant que Afficher "v n'est pas présent dans t".
Dans cette version, il y aura le même nombre de boucles, mais dans il y aura un nombre fini d'instructions donc indépendant de N.
Ainsi, la complexité de cet algorithme est de l’ordre du logarithme de la longueur du tableau.
Voici le code en python de cet algorithme :
def recherche_dichotomique(val, tab):
index_debut = 0
index_fin = len(tab)-1
while (index_fin - index_debut) >= 0:
centre = (index_debut + index_fin)// 2
if tab[centre] == val:
return True
elif tab[centre] > val:
index_fin = centre - 1
else:
index_debut = centre + 1
return FalsePour s’assurer que le programme ci-dessus fonctionne correctement,il faut se poser deux questions importantes :
Nous allons traiter ces deux questions et en donner des réponses rigoureuses.
La fonction recherche_dichotomique contient une boucle non bornée, une boucle while, et pour être sûr de toujours obtenir un résultat, il faut s’assurer que le programme termine, que l’on ne reste pas bloqué infiniment dans la boucle.
Pour prouver que c’est bien le cas, nous allons utiliser un variant de boucle.
Variant de boucleIl s’agit d’une quantité entière qui:
Si l’on arrive trouver une telle quantité, il est évident que l’on va nécessairement sortir de la boucle au boût d’un nombre fini d’itérations, puisque un entier positif ne peut décroître infiniment.
- doit être positive ou nulle pour rester dans la boucle;
- doit strictement décroître (ou croître) à chaque itération.
Preuve de la terminaison
Le variant de boucle dans notre cas est V=(index_fin - index_debut). V est évidemment un entier positif si tab est un tableau non vide.
Vérifions que V décroit. Pour cela regardons les 3 cas de figure :
Donc V décroit strictement à chaque itération, donc cela garantit la terminaison de la boucle.
Pour prouver la correction du programme, nous allons utiliser un invariant de boucle. Nous allons utiliser l’invariant de boucle suivant:
Inv: Si val est présente dans tab, c’est nécessairement à un index compris entre index_debut et index_fin (inclus).
INITIALISATION : on doit montrer que l'invariant de boucle est vrai avant la première itération de la boucle.
Avant de rentrer dans la boucle, le tableau est complet, Inv est évident.
CONSERVATION : on doit montrer que si l'invariant de boucle est vrai avant une itération de la boucle, il le reste à la fin de l'itération.
Si val est présente dans tab à l'entrée de la boucle, c’est nécessairement à un index compris entre index_debut et index_fin (inclus).
trois cas sont à examiner:
tab[centre] = val, alors la correction du programmes est évidente ;
tab[centre] < val, alors l'index de val est compris entre centre + 1 et index_fin avec index_debut = centre + 1;
tab[centre] > val, alors l'index de val est compris entre index_debut et centre - 1 avec index_fin = centre - 1.
TERMINAISON : val appartient à un tableau vide, donc n'appartient pas à tab.