ALGORITHME DE RECHERCHE DICHOTOMIQUE

Commentaire de cosmobob le 27/07/2005 10:17:58

salut,
t'as oublié de dire qu'il fallait que ton tableau soit trié pour que ca marche bien, ce qui est une condition très forte.

a+

Commentaire de BruNews le 27/07/2005 10:37:03 administrateur CS

Clair que pour une recherche dichotomique faut que le tableau soit trié.

Quel besoin de la récursivité ??? On fait idem en itératif et c'est nettement plus rapide, on supprime en plus un param en ne donnant que le nbr d'élements du tableau.

Commentaire de BruNews le 27/07/2005 11:35:09 administrateur CS

allez c'est pas dramatique le niveau de la source.

Lui fournir un exemple itératif sera plus profitable (enlevez les goto s'ils vous font mal aux yeux):

int __stdcall RechDicho(const int *parray, int nelem, int val)
{
  int i, n; // i = PIVOT CENTRAL
  if(nelem <= 0) goto notFOUND;
  i = nelem / 2;
  if(parray[i] == val) goto okFOUND;
  if(parray[i] < val) {
    while(++i < nelem) {
      n = parray[i];
      if(n == val) goto okFOUND;
      if(n > val) break; // ON SORT ILLICO
    }
  }
  else {
    while(--i >= 0) {
      n = parray[i];
      if(n == val) goto okFOUND;
      if(n < val) break; // ON SORT ILLICO
    }
  }
notFOUND: return -1;
okFOUND: return i;
}

Commentaire de deck_bsd le 27/07/2005 11:49:44

Merci BruNews pour l'exemple itératif, mais je l'avai déjà fait :D, oui car c'était un exercice de labo algo et nous avions du faire les deux. Mais j'ai réfèrée mettre le récursif, car il est plus facile a la compréhension.
Comme le dit mon profs de concept, il est parfois préfèrable de ne pas optimiser au maximum un code , car il se pourrai que après celui-ci ne sois plus très compréhensible. Donc je préfères 100fois utilisé un peu plus de mémoire et que mon code soit compréhensible que de tout rétressir lol, surtout que maintenant la mémoire n'est plus une denrée rare comme dans le temps. Mais c'est vrai qu'il faut optimiser sont code, mais pas jusqu'a le rendre incompréhensible. Mais tu a raison que pour la recherche dico on aurai pus prendre l'itératif.

PS: j'ai mis cette source dans initié car, un débutant ds la programmation en générale ne sais pas ce qu'est un algorithme ou alors en à une idée très vague.

++All

Commentaire de LiBe444 le 27/07/2005 12:37:22

Tiens un problème de partiel tant qu'on y est.
Est ce que la recherche dicothomique marche sur un tableau tel que pour tout i, |T[i+1]-T[i]|<=1 ?
Essaie et conclue avec un exemple.
S'il est vrai que tu ne t'es jamais posé de telles questions, reflechir dessus te fera prendre de l'avance si tu veux faire de l'informatique ton metier.

Commentaire de deck_bsd le 27/07/2005 13:37:00

Libe444 , Pour ton 1er problème ma réponse, sur le test d'une valeur supérieur etait évidement incorporer ds la recherche dicotomique, je voulai juste dire, que on test comme dans l'algo que g mis si le tableau n'est pas vide, si c'est le cas, on effectue une 1er fois la recherche , une fois cette recherche effectuée on fait alors le test que j'ai décrit plus haut, si le test est positif on continue la recherche dico, si il est négatif, c'est qu'il n'y a plus de valeur et donc la recherche s'arrèt et l'on renvoie le résultat.
Pour ce qui est dut 2ième, je doit avouer que ca me parait bizar, je doit prouver en faite que pour tout i, si on fait la valeur pointée par l'indice i + 1 - cette mm valeur on doit aboutir a une résultat plus petit ou égale a 1?

Commentaire de deck_bsd le 27/07/2005 13:45:33

a première vue pour ton problem n°2 je dirai oui car vu que c'est un tableau d'élément trier, le chiffre après est tjrs supérieur ou égale a au précédent donc si on le soustrait le 2ième du prémié on tombe forcément en négatif ou = a 1, sauf si l'entier est 0. Mais je v y réfléchir plus longuement. Je sais que tu fait ca pour comment dirai je me faire souffrire lol mais c'est quand mm cool.

Commentaire de BruNews le 27/07/2005 13:49:42 administrateur CS

Révisons les classiques, rien de tel que Robert Sedgewick:

int __stdcall RechDicho(const int *parray, int nelem, int val)
{
  int pos, n, i;
  if((n = nelem) <= 0) goto notFOUND;
  if(val == parray[0]) return 0;
  pos = 1;
  while(n >= pos) {
    i = (pos + n) / 2;
    if(val < parray[i]) n = i - 1;
    else pos = i + 1;
    if(val == parray[i]) return i;
  }
notFOUND: return -1;
}

Commentaire de LiBe444 le 27/07/2005 14:30:17

N'oublie pas la valeur absolue dans l'inegalité |T[i+1]-T[i]|<=1
Cela signifie que le tableau varie d'amplitude maximale un de proche en proche ; exemple :

la suite 8 7 7 6 5 4 5 6 7 8 9 9 8 7 6 5 4 3

Aucun ordre total ne régit deux éléments isolés.

Commentaire de deck_bsd le 27/07/2005 14:44:05

Mais avec cette suite la rech dico ne saurai pas fonctionnée ou partiellement

Commentaire de vecchio56 le 27/07/2005 15:37:39 administrateur CS

LiBe444 j'ai pas trop compris ton problème... ya même pas de piège, la réponse est évidemment non

Commentaire de LiBe444 le 27/07/2005 20:21:51

Vecchio la réponse est oui justement (je l'ai étudié en plus). Fais toi un petit exemple.

Quand on varie de un ou de zéro en croissant ou en décroissant, prendre un plus petit intervalle implique que la valeur se trouve dedans. Or nécessairement elle y est puisque on a par hypothèse soit que la valeur n'y est pas (et dans ce cas pas dans le tableau tout entier) soit elle y est au moins une fois car T[inf]<x et T[sup]>x ou alors T[inf]<x et T[sup]>x. Comme les valeurs de T sont "surjectives" (pour vous l'imager bien que T ne soit pas une fonction), x figure obligatoirement dans le sous ensemble. Donc la recherche dicothomique marche.
Un doute ? Demandez le à votre professeur d'informatique (même s'il est à la plage ça peut bouillonner)

Commentaire de vecchio56 le 28/07/2005 15:16:30 administrateur CS

Je crois que les professeurs sont en vacances actuellement, tu peux donc nnous montrer ici comme tu fais ca avec dichotomie (j'ai pas trop compris ton explication)
Pour le coup du surjectif, tu parle de l'application x->T[x]? Celle la a l'air plutot injective non? j'ai un peu oublié tout ca...

Commentaire de LiBe444 le 29/07/2005 19:27:43

Essayons :
RD(#(2,1,2,3,2,3,4,5),1,plancher(1+8/2)) = RD(#(2,1,2,3),1,plancher(1+4/2)) = 2

où #() est un tableau en Scheme.

Essayez le avec mon interpreteur de langage "K" (c'est mon script que personne ne regarde)

Commentaire de cosmobob le 01/08/2005 11:42:59

je pense qu'il a du mal a piger lui meme ce qu'il raconte ...
ca n'explique pas pourquoi tu t'orientes vers la sous partie gauche du tableau plutot que vers la droite ce que tu racontes...

Commentaire de cosmobob le 02/08/2005 00:52:31

comment voir que 2 est a gauche ou a droite ?
tu peux pas le deduire de la valeur des extrémités de ton sous tableau si le tableau est pas ordonné

Commentaire de deck_bsd le 02/08/2005 08:59:26

Lol oui mais sont programme lui il n'en à pas ptdr. Ckler aucun moyen de savoir de quelle coté il est le 2.


++All

Commentaire de deck_bsd le 05/08/2005 19:39:03

oui attendons.

Commentaire de LiBe444 le 07/08/2005 14:41:06

RD n'est rien de plus qu'une recherche dicothomique sur le modèle proposé par DECK_BSD, mais dans une écriture plus formelle.

Commentaire de LiBe444 le 10/08/2005 23:53:16

Justement, Deck_Bsd l'a écrite, c'est la fonction de prototype int rechDich (int D_intt[], int D_intvaleurRecherchee, int D_intborneInf, int D_intborneSup) ;