Recherche dans un array (binary search)

cs_mast
Messages postés
24
Date d'inscription
dimanche 17 juin 2001
Statut
Membre
Dernière intervention
3 octobre 2006
- 3 oct. 2006 à 02:21
cs_mast
Messages postés
24
Date d'inscription
dimanche 17 juin 2001
Statut
Membre
Dernière intervention
3 octobre 2006
- 3 oct. 2006 à 18:56
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;
}

3 réponses

cs_mast
Messages postés
24
Date d'inscription
dimanche 17 juin 2001
Statut
Membre
Dernière intervention
3 octobre 2006

3 oct. 2006 à 02:40
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
0
ria94
Messages postés
97
Date d'inscription
mercredi 28 mai 2003
Statut
Membre
Dernière intervention
3 octobre 2006

3 oct. 2006 à 17:54
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;


}
0
cs_mast
Messages postés
24
Date d'inscription
dimanche 17 juin 2001
Statut
Membre
Dernière intervention
3 octobre 2006

3 oct. 2006 à 18:56
J'ai trouve l'erreur hier, la boucle while aurait du etre while (left <= right), sinon on saute le dernier cas ;)

Merci
- Alex
0