Recherche dichotomique.

Introduction.

Rechercher des données est une chose courante dans la vie de tous les jours (dictionnaire, annuaire, pour faire vos moyennes,...), autant qu'en informatique. Certaines entreprises ont des milliards de données (Google par exemple) et elle doivent rapidement y avoir accès.
Chercher une information dans un tableau non trié a un coût proportionnel à la taille du tableau \(\Theta(n)\) mais il existe un algorithme meilleur en complexité : l'algorithme de recherche dichotomique mais il demande d'avoir les données triées. Le nombre d'étapes de l'algorithme est égal au plus petit nombre k tel que 2^k > taille des données. Ce nombre est égal à E(log₂(taille des données) + 1 (E partie entiére, et log₂ une fonction du programme de terminale. L'algorithme est en \(\Theta(ln(n))\)

Avec la recherche dichotomique la recherche des mots dans un dictionnaire de 35 000 mots se fait en 16 étapes. Si rechercher dans un tableau de taille 1000 < 2¹⁰ se fait en 1s (avec un des deux algortithmes naif ou dichotomique) alors rechercher dans un tableau de taille 1000000= 1000 × 1000 < 2²⁰ se fait en 1000 s dans la méthode naive et en 2s avec la dichotomie.

La recherche dichotomique utilise un procédé algorithmique appelé "diviser pour régner" (comme le tri fusion évoqué au précédent cours).

Algorithme

Algo

Le principe est simple :

Supposons qu'un tableau tab soit ordonné et considérons deux nombres entiers 0 ≤ borne_inf < borne_sup < taille du tableau -1, soit m le nombre que l'on cherche. On veut savoir s'il exite un indice i (avec borne_inf ≤ i ≤ borne_sup) tel que tab[i] = m. Il y a pour l'instant borne_sup-borne_inf + 1 choix possibles.

Soit milieu la partie entière de \(\frac{borne\_inf+borne\_sup}{2}\), notons que milieu est entier et compris entre borne_inf et borne_sup alors on a trois cas :

tab[milieu] = m, et on a terminé milieu est un indice qui convient.
tab[milieu] < m, alors forcément si l'indice i existe il doit être compris entre milieu + 1 et borne_sup. Le nombre de possibilités est alors au plus de :
borne_sup-(milieu+1) + 1 = borne_sup - milieu < borne_sup-(\(\frac{borne\_inf+borne\_sup}{2}\))-\(\frac{1}{2}\) = \(\frac{borne\_sup-borne\_inf+1}{2}\)
on a donc divisé le nombre de possibilité par deux.
tab[milieu] > m, alors forcément si l'indice i existe il doit être compris entre borne_inf et milieu -1. Le nombre de possibilités est alors au plus de :
milieu-1-borne_inf+1 = milieu - borne_inf < (\(\frac{borne\_inf+borne\_sup}{2}\)) - borne_inf = \(\frac{borne\_sup-borne\_inf}{2}\) < \(\frac{borne\_sup-borne\_inf+1}{2}\)
on a donc divisé le nombre de possibilité par deux.

On répète alors l'opération avec les bornes nouvelles. Comme le nombre d'indice est entier et que l'on divise à chaque fois par deux au bout d'un moment le nombre de choix va valoir 1 (si on ne trouve pas l'indice avant). et il suffit alors de tester cette valeur.

Essayez sur l'exemple ci dessous :

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24
0	1	2	3	5	8	12	15	20	25	30	33	38	40	42	48	50	55	60	65	70	72	80	90	100

Où :

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31	32	33	34	35	36	37	38	39	40	41	42	43	44	45	46	47	48	49
0	1	2	3	5	8	12	15	20	25	30	33	38	40	42	48	50	55	60	65	70	72	80	90	100	101	105	107	108	110	112	118	122	125	130	132	140	145	150	152	160	162	170	175	177	180	182	188	190	200

Voici le programme python de recherche dichotomique dans un tableau trié.

Q.C.M.

La complexité (en comparaisons) de la recherche dans un tableau non trié de taille n est de l'ordre de :

n
n²
nln(n)²
ln(n)²+4

Q.C.M.

La complexité (en comparaisons) de la recherche dans un tableau trié de taille n avec la recherche dichotomique est de l'ordre de :

n
n²
nln(n)
ln(n)

Q.C.M.

Pour trouver une valeur dans un tableau trié de 300 valeurs avec l'algorithme de recherche dichotomique, il faut au maximum :

7 comparaisons.
8 comparaisons.
9 comparaisons.
10 comparaisons.

Q.C.M.

En combien de calcul du milieu l'algorithme de dichotomie va trouver 3 dans le tableau [1,2,3,4,5,6,7]

1
2
3
4

Q.C.M.

La recherche dichotomique fait partie des algorithmes :

diviser pour régner.
gloutons.
dynamiques.
naifs.

Q.C.M.

Modifier le programme de recherche dichotomique pour qu'il donne en plus le nombre de fois où il effectue la boucle.
On cherche le nombre 9 dans le tableau suivant :
0 1 2 3 4 5 6 7 8 9 10 11 12

Indiquer pour chaque étape de l'algorithme de recherche dichotomique les nombres du tableau encore possibles.

clicker pour voir la solution

Pour chaque nombres du tableau suivant dire en combien d'étapes (de la boucle while) l'algorithme de recherche dichotomique va le trouver :
0 1 2 3 4 5 6 7 8 9 10 11 12

clicker pour voir la solution

Programmer la méthode naive.
Ajouter votre programme de recherche naive (appelée naive(valeur,tab) et la recherche_dichotomique et le programme suivant puis effectuer la recherche de 10 000 000 dans le tableau [0,1,2,3,... 10000000] en utilisant la fonction comparaison.

Les deux versions suivantes implémentent la recherche dichotomique mais avec des petites variantes, les critiquer.

Pour aller plus loin

La vidéo ci-dessous parle des algorithmes gloutons (que nous verrons bientôt) et de la méthode de dichotomie :

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24
0	1	2	3	5	8	12	15	20	25	30	33	38	40	42	48	50	55	60	65	70	72	80	90	100

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31	32	33	34	35	36	37	38	39	40	41	42	43	44	45	46	47	48	49
0	1	2	3	5	8	12	15	20	25	30	33	38	40	42	48	50	55	60	65	70	72	80	90	100	101	105	107	108	110	112	118	122	125	130	132	140	145	150	152	160	162	170	175	177	180	182	188	190	200

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24
0	1	2	3	5	8	12	15	20	25	30	33	38	40	42	48	50	55	60	65	70	72	80	90	100

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31	32	33	34	35	36	37	38	39	40	41	42	43	44	45	46	47	48	49
0	1	2	3	5	8	12	15	20	25	30	33	38	40	42	48	50	55	60	65	70	72	80	90	100	101	105	107	108	110	112	118	122	125	130	132	140	145	150	152	160	162	170	175	177	180	182	188	190	200

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24
0	1	2	3	5	8	12	15	20	25	30	33	38	40	42	48	50	55	60	65	70	72	80	90	100

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31	32	33	34	35	36	37	38	39	40	41	42	43	44	45	46	47	48	49
0	1	2	3	5	8	12	15	20	25	30	33	38	40	42	48	50	55	60	65	70	72	80	90	100	101	105	107	108	110	112	118	122	125	130	132	140	145	150	152	160	162	170	175	177	180	182	188	190	200