recherche dichotomique Fermé

Question

Bonsoir:

je veux qlq m'expliquer facilement le principe de RECHERCHE DICHOTOMIQUE  svp 

et MERCI

crapoulou · Answer

Bonsoir,

Essaye de regarder ici, cela peut t'aider (si ce n'est pas déjà fait) :
https://fr.wikipedia.org/wiki/Dichotomie
http://www.siteduzero.com/tutoriel-3-32948-recherche-dichotomique.html

Le but est de rechercher ta valeur dans un vecteur trié.
Tu procèdes par moitié :
Tu coupes ton vecteur en 2 et tu regarder si c'est inférieur ou supérieur à la valeur que tu recherches.
En fonction de cela, tu cibles ta recherche dans ton vecteur.
(variables inf : borne inférieure de recherche et sup : borne supérieure de recherche).

A la fin, tu regardes si sup = val (valeur cherchée).

Je t'ai expliqué grossièrement mais avec les liens et ça tu devrais y voir plus clair.
Qu'est-ce que tu n'as pas compris plus précisément ?

Pacorabanix · Answer

en fait, on fait naturellement un truc dans le même genre lorsque on recherche un nom dans un annuaire par exemple :
xxxxxxxxxx

On cherche John

On ouvre l'annuaire au milieu. On tombe sur Martin. Donc on est trop loin.
On prend alors le milieu de la première moitié.

Imagine on tombe sur Jean-louis.

On est pas assez loin, il faut rechercher dans le quart après jean-louis.
Etc... jusqu'à ce qu'on tombe pile sur John.

Adnane91 · Answer

Trés bien :
 
donc si je comprends bien le principe de la recherche dichotomique 

1-c'est de chercher une valeur sur la liste de N valeur 
2-l'avantage de la rechcerche dochotomique consiste de eviter l'ancien methode de recherche ( d'une facon linéaire ) .. mais couper la liste (sur2) et comparer la valeur rechercher avec L( I ) de milieu 
Si Val = L( I )  ===> ( Mission succes ) 
Si Val > L( I )  ===> ( completer la rechcerche sur la moitié L( I )SUP )
Sinon             ===>  (completer la recherche sur la moitié L( I )INF ) 

la question Mnt : pour completer la recherche soit sur la moitié sup ou inf est ce qu'on va repeter le meme principe c'est a dire diviser(2) la moitié(SUP) - (si on cherche par exemple dans la moitié SUP) et verifier si L(I-moitié) sup ou inf ..... et ainsi de suite ....OU il y'a une autre methode ?!!

Pacorabanix · Answer

la question Mnt : pour completer la recherche soit sur la moitié sup ou inf est ce qu'on va repeter le meme principe c'est a dire diviser(2) la moitié(SUP) - (si on cherche par exemple dans la moitié SUP) et verifier si L(I-moitié) sup ou inf ..... et ainsi de suite ....OU il y'a une autre methode ?!!

Oui c'est bien ça : selon si Val > L( I ) ou Val < L( I ), on réapplique le même procédé sur le tableau supérieur ou inférieur respectivement. Donc on refait une recherche dichotomique, mais pas sur le même tableau : un tableau environ deux fois plus petit

C'est donc un procédé récursif, ce qui a le mérite d'être "élégant" (facile à coder et à comprendre en général)


En comparaison à la recherche linéaire qui est O(N) en complexité, la recherche dichotomique est O(log2(N)).
C'est donc très efficace.

Adnane91 · Answer

Merci  Pacorabanix,
 Donc l'algorithme est comme ca 

1-donner le nombre de valeur de la liste (NB) (pour i de 0 a NB-1)
2-on va trier la liste (suivant la methode de tris par(BULLE) par exemple ) pour effectuer la recherche sans prob
3-donner a l'utilisateur la valeur rechercher 
4-si Val=L((NB-1)/2) alors , ecrire (val trouvé)
5-sinon (c'est a dire val  est <> soit sup ou inf ) 
6-repeter 
( la question ICI ) ====> l'essentielle ICI
Jusqu'a

Recherche dichotomique

5 réponses

Discussions similaires