La recherche par dichotomie

La fiche de cours est ici.

Recherche séquentielle d'un élément dans un tableau

On cherche à déterminer si une valeur donnée se trouve ou pas dans un tableau.

Voila un travail que vous avez déjà fait il n'y a pas si longtemps, cette première partie devrait donc aller assez vite...

écrire l'algorithme qui permet de rechercher la présence d'une certaine valeur dans un tableau par recherche séquentielle.
Quelle est la complexité en temps de l'algorithme utilisé ici ? Justifier.
Écrire une fonction recherche_sequentielle qui :
- prend comme paramètre un tableau d'entiers et une valeur entière à y rechercher
- renvoie l'indice de la valeur dans le tableau si la valeur n se trouve dans le tableau, la valeur - 1 si elle ne s'y trouve pas
tester la fonction avec quelques valeurs présentes ou non dans le tableau.

def recherche_sequentielle(tab, valeur): pass L = [65, 42, 10, 91, 14, 34, 89, 45, 97, 20, 80, 84, 79, 25, 86, 90, 13, 71, 43, 51, 15, 96, 6, 47, 57, 70, 54, 62, 16, 33, 36, 83, 59, 93, 44, 66, 26, 81, 5, 72, 23, 21, 32, 9, 8, 76, 18, 64, 73, 52]

SOLUTION

N'y a-t-il pas une manière plus efficace ?

Voila un petit jeu pour commencer : le nombre à deviner.

Un nombre aléatoire compris entre 1 et 100 est généré aléatoirement.
Vous devez le retrouver en moins de 10 essais.

1 Si on avait utilisé la recherche séquentielle, combien d'essais auraient été nécessaires dans le pire des cas ? 2. Combien d'essais faut-il ici en moyenne pour deviner le nombre ? 3. Quelle est la précondition que respectent ( forcément...) les nombres qui fait que la technique utilisée ici est plus efficace que de proposer séquentiellement des valeurs ?

SOLUTION

Un algorithme de recherche plus subtil : la recherche par dichotomie

Cet algorithme, ainsi que le précédent ( recherche séquentielle ) font partie de la liste des algorithmes à connaître pour l'épreuve pratique du BAC.

Principe

On va donc se servir, pour rechercher la présence d'une valeur dans un tableau, du fait que si celui-ci a été préalablement trié, on va pouvoir utiliser une méthode de recherche beaucoup plus efficace, la recherche par dichotomie. Dichotomie veut dire littéralement "couper en deux".

L'idée est de couper le tableau en 2 parties; on se retrouve avec 2 sous-tableaux de taille identique ( à un élément près dans le cas où le nombre total d'éléments du tableau est impair, mais ça ne change rien ).
On garde uniquement le sous-tableau qui peut contenir la valeur recherchée : comme les sous-tableaux sont aussi triés, ce n'est pas difficile à déterminer, il suffit de comparer la valeur recherchée avec l'élément délimitant les deux sous-tableaux, c'est à dire l'élément au milieu du tableau.
On recommence le processus jusqu'au moment où l'on se retrouve avec un tableau contenant un seul élément : si l'élément unique de ce tableau n'est pas l'élément recherché, l'algorithme renvoie FAUX, et VRAI sinon ( et éventuellement, l'indice dans le tableau de la valeur recherchée ).

Nombre d'éléments

Valeur à rechercher :

Nombre d'étapes :

Algorithme

Voici l'algorithme de la recherche dichotomique; la précondition est que le tableau est trié :


tant que le tableau n'est pas réduit à UN SEUL élément :
		si la valeur est égale à l'élément au milieu du tableau :
			alors on a trouvé la valeur, on renvoie VRAI et l'indice de la valeur
		sinon :
			si la valeur est PLUS PETITE que l'élément au milieu :
				alors elle se trouve forcément dans la partie GAUCHE du tableau : on recommence la recherche dans la partie GAUCHE du tableau
			sinon si la valeur est PLUS GRANDE que l'élément au milieu :
				alors elle se trouve forcément dans la partie DROITE du tableau : on recommence la recherche dans la partie DROITE du tableau

on a réduit le tableau à un seul élément, et on n'a pas trouvé la valeur : on renvoie donc FAUX

Avant de se lancer dans le code, il faut bien comprendre comment nous allons pouvoir coder ce qui apparaît dans l'algorithme dans les expressions "la partie GAUCHE du tableau" et "la partie DROITE du tableau".

Une possibilité serait de supprimer une partie du tableau, pour ne garder que celle dans laquelle on poursuivra la recherche ( la partie "droite" ou la partie "gauche").
Cependant, cela nécessiterait de modifier le tableau en mémoire, ce que l'on va chercher à éviter...

Nous allons plutôt conserver le tableau inchangé, et indiquer à l'algorithme dans quelle "zone" du tableau il doit effectuer la recherche : pour cela, nous allons utiliser 3 variables ( appelées ici pointeurs ) g ( pour "gauche" ), m ( pour "milieu"), et d ( pour "droite" ), qui serviront à "délimiter" les deux parties "gauche" et "droite" à chaque étape de la recherche :

g = indice du premier élément
d = indice du dernier élément
m = indice de l'élément au milieu

La partie "gauche" correspondra alors aux éléments [g ; m[, et la partie "droite" aux éléments ]m ; d].

Les trois variables seront modifiées au cours de la recherche pour indiquer "où" la recherche doit se faire.

Dans l'image ci-dessous vous pourrez comprendre l'évolution des valeurs des variables g, m et d pour la recherche du nombre 16 dans le tableau fourni.

Compléter le tableau ci-dessus pour la recherche de la valeur 89 dans le tableau.
quelle condition sur les variables g et d est vérifiée "tant que le tableau n'est pas réduit à un seul élément" ?
comment est calculée la valeur de m à partir de celle de g et d ?
lorsque la recherche doit se poursuivre ensuite sur "la partie GAUCHE du tableau", quelle variable faut-il modifier, et comment ?
mêmes questions pour la recherche sur "la partie DROITE du tableau"
écrire alors en pseudo-code l'algorithme complet de la recherche dichotomique.

SOLUTION

Codage

Coder en Python la fonction recherche_dicho réalisant la recherche dichotomique d'une valeur n dans un tableau tab trié.

Cette fonction renvoie l'indice de la valeur dans le tableau si elle s'y trouve, et -1 dans le cas contraire.

def recherche_dicho(tab, valeur): pass # TESTS L = [5, 6, 8, 9, 10, 13, 14, 15, 16, 18, 20, 21, 23, 25, 26, 32, 33, 34, 36, 42, 43, 44, 45, 47, 51, 52, 54, 57, 59, 62, 64, 65, 66, 70, 71, 72, 73, 76, 79, 80, 81, 83, 84, 86, 89, 90, 91, 93, 96, 97] recherche_dicho(L, 26) == True recherche_dicho(L, 5) == True recherche_dicho(L, 97) == True recherche_dicho(L, -5) == False recherche_dicho(L, 46) == False recherche_dicho(L, 154) == False

SOLUTION

Retour sur la complexité

Un nouveau coût en temps...

On a déjà parlé de complexité d'un algorithme quand on a travaillé sur la recherche "naïve" dans un tableau non trié ( Rappel : c'est O(n) ).
Nous allons essayer de trouver la complexité de l'algorithme par dichotomie

Il faut donc trouver le nombre d'étape nécessaires pour trouver un élément par dichotomie dans le pire des cas.

Ce que l'on cherche ici c'est le nombre d'étapes maximum pour gagner au jeu "deviner un nombre" en jouant "par dichotomie" (si on commence à jouer au hasard ).

1. Compter le nombre d'étapes nécessaires pour être sur de gagner au jeu pour un nombre compris entre 1 et 10 : 2. Compter le nombre d'étapes nécessaires pour être sur de gagner au jeu pour un nombre compris entre 1 et 20 : 3. Compter le nombre d'étapes nécessaires pour être sur de gagner au jeu pour un nombre compris entre 1 et 100 :

Mais on cherche une relation générale pour une partie de jeu avec un nombre compris entre 1 et n...
La technique est donc de compter combien de fois il faut diviser par 2 le nombre n pour arriver à 1.
C'est assez simple quand on travaille avec des puissances de deux :

Compter combien de fois il faut diviser par 2 le nombre 1024 pour arriver à 1 : Compter combien de fois il faut diviser par 2 le nombre 2048 pour arriver à 1 : Compter combien de fois il faut diviser par 2 le nombre 4096 pour arriver à 1 :

Bon ça commence à être un peu long tout ces tâtonnements !
Heureusement il existe une fonction mathématique qui fait ce calcul à notre place : c'est le logarithme de base deux.
Pour le trouver sur votre calculatrice Numworks, c'est très simple :

Appuyez sur la touche toolbox puis choisissez la troisième possibilité dans le menu ( pour les autres calculatrices appelez le professeur ).

Si vous n'avez pas votre calculatrice sous la main vous pouvez aller ici :https://www.numworks.com/fr/simulateur/.

Calculer log₂(10) = Calculer log₂(20) = Calculer log₂(100) = Calculer log₂(1024) = Calculer log₂(2048) = Calculer log₂(4096) =

Nous dirons alors que :

La complexité de la recherche dichotomique dans un tableau trié de n éléments est en O(log₂(n)).

Vous pouvez simplement retenir que le logarithme en base 2 de n est le nombre de fois qu'il faut diviser n par 2 pour obtenir 1.

Conséquence : quand le nombre de données double, l'algorithme ne nécessite qu'une seule étape de plus; quand il est quadruplé, 2 étapes de plus, etc...

Cette notion est très importante, nous la retrouverons lors du tri de liste ou de l'étude des arbres binaires en terminale.

Pour conclure

Pour comparer l'efficacité des deux algorithmes vus dans ce chapitre ( recherche séquentielle et dichotomique ), installer le module Matplotlib et visualiser les deux courbes montrant l'évolution du coût en temps de chacun des deux en fonction de n :

import matplotlib.pyplot as plt from random import randint from timeit import timeit x = [10**i for i in range(3,7)] y1 = [] y2 = [] for n in x: L = [randint(1,n//10) for i in range(n)] val = randint(1, n//10) t1 = timeit(stmt="recherche_sequentielle(L, val)", globals=globals(), number=1) L.sort() t2 = timeit(stmt="recherche_dicho(L, val)", globals=globals(), number=1) y1.append(t1) y2.append(t2) plt.plot(x, y1, label="rech_sequ") plt.plot(x, y2, label="rech_dicho") plt.xlabel("n") plt.ylabel("durée d'éxécution") plt.legend() plt.show()

Que constate-t-on ??

Comme toujours quand on parle de complexité, la différence entre les deux algorithmes apparaît pour de grandes valeurs de n.

Mission fiscale : comparaison des méthodes de recherche

Aujourd’hui nous faisons partie de l'équipe de codeurs du ministère des finances qui lutte contre l'évasion fiscale.
Notre objectif :
Être capables de retrouver rapidement des numéros de compte ou des sommes précises dans des listings dont le volume peut quelquefois dépasser le Teraoctet !.

Pour cela nous allons, en amont de ces recherches, tester différentes techniques de recherche d'élément dans un tableau.

Le "pack" dont vous disposez

Vous pouvez télécharger ici un pack de fichiers.
Vous trouverez dans ce pack :

Un fichier python tests_recherche.py contenant des fonctions qui vous permettront de mener à bien votre recherche.
6 fichiers de 80 octets à 8Mo contenant des entiers triés par ordre croissant, pris entre 1 000 000 et 10 000 000.

Le travail à réaliser

Grâce à ce pack et à vos connaissances (et à votre travail de la semaine dernière !), vous devez rédiger un rapport sous open office présentant les différentes performances des trois fonctions de recherche :

La recherche naïve
La recherche par dichotomie
La recherche implémentée dans python

Vous devrez pour cela utiliser le module timeit dont vous pourrez trouver un exemple d'utilisation ici.
votre rapport devra contenir :

trois courbes présentées sur le même graphique montrant l'évolution de la durée de recherche d'un nombre non présentdans les fichiers en fonction de la taille du fichier.
Une prévision du temps d'exécution du même test pour un fichier de 80Mo pour chacune des fonctions testées.
Une conclusion quant au choix de la méthode de recherche à utiliser
En annexe : le code complet qui vous a permis de réaliser ce test.