A voir également:
- Recherche dichotomique
- Recherche automatique des chaînes ne fonctionne pas - Guide
- Rechercher ou entrer l'adresse mm - recherche google - Guide
- Recherche photo - Guide
- Je recherche une chanson - Guide
- Rechercher ou entrer l'adresse 4 - recherche google ✓ - Forum Windows
5 réponses
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 ?
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 ?
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.
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.
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 ?!!
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 ?!!
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.
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.
Vous n’avez pas trouvé la réponse que vous recherchez ?
Posez votre question
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
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