Discussion :

[Saemina]

Bonjour à tous je débute en informatique et je voulais faire un algorithme qui permet de faire une recherche dichotomique dans un tableau avec la récursivité.
J'ai un problème dans mon code que je n'arrive pas à résoudre, quand je l’exécute il me dit qu'il y a une erreur de segmentation..
Pourriez vous m'aider à trouver ce qui ne va pas s'il vous plaît ? :/

Voilà mon code

Code C :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <time.h>
 
#define N 30
 
/* Fonction de comparaison de 2 entiers, utilisée par qsort */
int comp (const void * a, const void * b)
{
    return ( *((int*)a) - *((int*)b) );
}
 
/* Fonction d'affichage d'un tableau */
void afficheTableau(int t[], int size)
{
    int i;
    for (i=0; i < size; ++i)
        printf("%d ", t[i]);
    printf("\n");
}
 
bool rechercheDichotomique (int tab[], int elem, int indexL, int indexR){
 int milieu = (indexR+indexL)/2;
     if(elem == tab[milieu]) 
        return true;
     else
     {
        if (elem < tab[milieu]){ 
              rechercheDichotomique(tab,elem, indexL, milieu-1);}
        if (elem>tab[milieu]){
              rechercheDichotomique(tab,elem, milieu+1, indexR);}
     }
 
     return false;
}
 
 
int main() {
    int tab[N];
    int elem1, elem2;
    int i;
 
    //generation aleatoire des elements du tableau
    srand(time(NULL));
    for(i = 0; i < N; ++i) {
        tab[i] = rand()%100;
    }
 
    //tri du tableau
    qsort (tab, N, sizeof(int), comp);
 
    elem1 = tab[N-1];
    elem2 = 100;
 
    printf("Le tableau tab: \n");
    afficheTableau(tab, N);
 
 
    printf("Element à rechercher:");
    int elem;
    scanf("%d", &elem);
    int indexR = elem2;
    int indexL = elem1;
    rechercheDichotomique(tab,elem,indexL,indexR);
 
 
    return EXIT_SUCCESS;
}

[Pyramidev]

Bonjour,

Il y a une erreur algorithmique dans rechercheDichotomique : l'instruction return false; n'est jamais atteignable.
Si tu recherches un élément qui n'existe pas dans le tableau, tu as une récursivité infinie.

[dalfab]

Bonjour,
Il y a plusieurs problèmes:
Dans l'appel principal à rechercheDichotomique les 2 derniers paramètres doivent être des index, pas les valeurs que l'on trouve à ces index. Donc bool trouve = rechercheDichotomique(tab,elem,0,N);. Et ça serait peut-être intéressant d'afficher si l'élément à été trouvé!

Dans la fonction elle-même, il manque des cas à contrôler. Si la valeur n'existe pas dans le tableau, il risque de se passer n'importe quoi.
Par exemple si plus grand et milieu>=indexR ou bien si plus petit et milieu<indexL, c'est que la recherche a échoué, et il ne faut pas appeler la fonction récursivement, c'est là qu'il faut retourner false. Dans les autres cas on doit retourner ce que retourne l'appel récursif.

[Saemina]

J'ai essayé de corrigé ça, j'ai rajouté les différents cas quand l’élément n'est pas dans le tableau et si j'essaye de lancer le programme et de rechercher un élément qui n'est pas dans le tableau, il y a une erreur de segmentation
J'ai rajouté les cas:

Code C :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
if(milieu>indexR || milieu<indexL){
         return false;
     }
     if((elem>indexR) || (elem<indexL)){
         return false;
     }

[Sve@r]

J'ai essayé de corrigé ça, j'ai rajouté les différents cas quand l’élément n'est pas dans le tableau et si j'essaye de lancer le programme et de rechercher un élément qui n'est pas dans le tableau, il y a une erreur de segmentation
J'ai rajouté les cas:

if(milieu>indexR || milieu<indexL){
return false;
}
if((elem>indexR) || (elem<indexL)){
return false;
}

Bonjour

Ce n'est pas que ça qu'il faut faire.
Quand tu appelles ta recherche récursive sur une sous-partie du tableau (gauche/droite), il te faut d'une façon ou d'une autre renvoyer son résultat à l'appelant (qui étant la même fonction récupère alors ce résultat et le renvoie à l'appelant et etc.). Parce que là, tu appelles ta fonction et tu ne fais rien de ce qu'elle te retourne...

Code c :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
bool rechercheDichotomique (int tab[], int elem, int indexL, int indexR){
    int milieu = (indexR+indexL)/2;
 
    if(elem == tab[milieu]) return true;
    if (indexL == indexR) return false;
 
    if (elem < tab[milieu]) return rechercheDichotomique(tab,elem, indexL, milieu - 1);
    else return rechercheDichotomique(tab,elem, milieu + 1, indexR);
}

Après, évidemment, il faut l'appeler dans le main avec les bons paramètres parce que j'ai rien compris à tes calculs (c'est quoi ce "100" à la con qui arrive d'on ne sait où ??? c'est sûr que si le tableau n'a que 30 cases, il va pas trop aimer que tu lui demandes de chercher dans les 70 suivantes...)... et aussi afficher son résultat !!!

Code c :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
	printf("Element à rechercher:");
	int elem;
	scanf("%d", &elem);
	printf("%d\n", rechercheDichotomique(tab, elem, 0, N));

Ensuite (optimisation), tu transformes ta fonction en int et tu lui fais renvoyer "milieu" si elle trouve ou "-1" si elle ne trouve pas. Ainsi, au lieu d'avoir une bête fonction à qui tu demandes "pouvez-vous me le trouver" et qui te répond "oui je le peux", t'as une bath fonction à qui tu demandes "pouvez-vous me le trouver" et qui te répond "il est là"...

[Saemina]

J'ai corrigé ma fonction mais elle m'affiche tout le temps 1 alors que le nombre n'est pas présent dans le tableau..

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
bool rechercheDichotomique (int tab[], int elem, int indexL, int indexR){
    int milieu =(indexL+indexR)/2;
    if (indexL > indexR)
        return -1;
 
   if (elem == tab[milieu])
        return true;
 
    if (elem < tab[milieu])
        return rechercheDichotomique(tab, indexL, milieu-1, elem);
 
    else 
        return rechercheDichotomique(tab, milieu+1, indexR, elem);
 
}

Pour tester la fonction:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
	printf("Element à rechercher:%d\n",elem2);
	printf("%d\n", rechercheDichotomique(tab, elem2, 0, elem1));

[Sve@r]

J'ai corrigé ma fonction mais elle m'affiche tout le temps 1 alors que le nombre n'est pas présent dans le tableau..

Code c :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
bool rechercheDichotomique (int tab[], int elem, int indexL, int indexR){
    int milieu =(indexL+indexR)/2;
    if (indexL > indexR)
        return -1;
 
   if (elem == tab[milieu])
        return true;
 
    if (elem < tab[milieu])
        return rechercheDichotomique(tab, indexL, milieu-1, elem);
 
    else 
        return rechercheDichotomique(tab, milieu+1, indexR, elem);
 
}

Pour tester la fonction:

Code c :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
	printf("Element à rechercher:%d\n",elem2);
	printf("%d\n", rechercheDichotomique(tab, elem2, 0, elem1));

Que veux-tu qu'on te dise ??? Si tu fais retourner -1 via une fonction de type "bool" ben comme c'est différent de 0 le booléen est vrai et un vrai affiché au format "%d" donne 1.
Faut que t'arrêtes de faire le bébé et que tu te sortes un peu les doigts quoi. T'as un cerveau, c'est déjà pour t'en servir un minimum en apprenant les bases avant de solliciter les notres.

Accessoirement ta fonction est prévue pour recevoir le tableau, l'élément à chercher, l'index min et l'index max. Tout ça dans cet ordre strict.
Dans le main tu lui passes le tableau, elem2 (on va dire admettre que c'est l'élément à chercher), 0 (on dira que c'est l'index min, ça colle) et elem1. T'es sûr que elem1 est l'index max ???
Ensuite dans la récursion, là tu lui passes le tableau, puis tes index, puis l'élément à rechercher. Bref après le tableau rien d'autre dans le bon ordre. Je t'ai pourtant écrit une fonction correcte et sa façon de s'en servir. Tu aurais-pu au-moins t'en inspirer !!!