Recherche dans un array (binary search)

Question

Bonjour!

J'ai une array qui contient des prénoms, qui s'appelle x et une autre qui contient un nom seulement (name). J'ai écrit une function de "binary search" qui cherche si name se trouve dans l'array x. Pour une raison que j'ignore ça ne fonctionne qu'avec quelque noms. Note, mon array de prénoms, x, est en ordre alphabétique. Voici mon code, si vous avez des idées laissez-moi un message :)

Merci!
 - Alex

------------- 

int BSearch(char x[][NMAX], char name[])
{
int left, right, mid;
left = 0;
right = LSIZE;
while (left < right)
{
mid = (left+right) / 2;
if (strcmp(name, x[mid]) > 0)
{
left = mid + 1;
}
else if (strcmp(name, x[mid]) < 0)
{
right = mid - 1;
}
else
{
return mid + 1;
}
}
return -1;
}

cs_mast · Answer

Okay je viens de voir que le code était pas très clair ;) alors je post un url vers la source http://paste.lisp.org/display/27246

 - Alex

ria94 · Answer

Je pense ke l'erreur viens de la ligne mid = (left+right) / 2; Je t'explique vite fait imaginons t'as un tableau de 100noms Dans ton premier tour de boucle tu prend mid=(0+100)/2= 50 mettons que le noms soit dans la partie superieurtu vas donc faire left mid + 1; -->left 50+1=51 tu repasses dans ta boucle et tu refais un mid (left+right) / 2; --> (51+100)/2 75.5 Donc forcement tu check pa tous les cas Essaie ca : int BSearch(char x[][NMAX], char name[]) { int left, right, mid; left = 0; right = LSIZE; mid = (left+right) / 2; while(left < right) { if(strcmp(name, x[mid]) > 0) { mid++; } elseif(strcmp(name, x[mid]) < 0) { mid--; } else } return mid + 1; } leff++; } return -1; }

cs_mast · Answer

J'ai trouve l'erreur hier, la boucle while aurait du etre while (left <= right), sinon on saute le dernier cas ;)

Merci
- Alex

Recherche dans un array (binary search)

3 réponses

Votre réponse

Discussions similaires