Recherche dichotomique

Version imprimable

Bonjour je dois faire une recherche dichotomique...

Donc j'ai fais un petit programme mais il ne fonctionne pas j'ai une violation d'accès je suis débutant, si vous pouviez m'expliquer ? de quoi il s'agit j'ai essayé de passer par les pointeurs rien à faire...

Vous avez une idée ?

Code:

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
#include <stdio.h>
#include <stdlib.h>
int i;
 
int recherche(int tableau[99],int index,int minimum,int maximum){
 int milieu;   
  milieu = ( maximum - minimum ) / 2;
    if (minimum==maximum)
                          if (index==tableau[milieu])
                          return index; 
                          else return 0;
 
 
                          else
                          {
                               if (tableau[milieu]<=index){
 
                                                           return recherche(tableau,index,minimum+1,milieu);
 
 
                                                           }
                                                           else
                                                           {
 
                                                           return recherche(tableau,index,milieu,maximum);   
 
                                                           }; 
 
 
                          };
 
 
}
 
 
int main(){
    int tableau[99];
    tableau[0] = 1;
    printf("%d",tableau[0]);
 
    for(i=1;i<=99;i++){
                       tableau[i] = tableau[i-1] + i ;
                      printf(" - %d",tableau[i]); }
    scanf("%d",i);
    printf("%d",recherche(tableau,10,0,99));                  
    scanf("%d",i);
 
}

merci

06/01/2006, 16h47
fearyourself
Quelques erreurs typiques:
Code:

1 2 3 for(i=1;i<=99;i++) tableau[i] = ..
or ton tableau est défini avec int tableau[99]; , les indices vont donc de 0 à 98...
Code:

1 2 scanf("%d",i);
est faux,
Code:

1 2 scanf("%d",&i);
est juste mais scanf est déconseillé, voir les pages du forums pour une meilleure solution...
Code:

1 2 milieu = ( maximum - minimum ) / 2;
n'est pas le milieu
Code:

1 2 milieu = ( maximum + minimum ) / 2;
l'est...
Code:

1 2 3 4 5 if (index==tableau[milieu]) return index; else return 0;
est une erreur puisque ton élément peut être à l'indice 0 (si tu cherches 1) par exemple, c'est le premier élément de ton tableau (pourquoi d'ailleurs?)

Ensuite, je ne vois pas pourquoi tu fais minimum+1 dans ton 1er appel récursif, rien ne prouve que l'élèment ne se trouve pas à tableau[minimum], tu ne l'as pas testé...

Jc
06/01/2006, 16h54
ep31

La condition d'arrêt de ta fonction récursive est :

Code:

if (minimum==maximum)

et à première vue, je dirai que ta fonction part en boucle infinie et tu dois avoir un stack overflow non ?

....

Hargh ca ne fonctionne toujours pas !
En faite dev c++ démarre le programme et là il se ferme tout de suite...
Quand je debug des fois il me met access violation (segmentation fault)

Code:

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
#include <stdio.h>
#include <stdlib.h>
int i;
 
int recherche(int tableau[100],int index,int minimum,int maximum){
 int milieu;   
  milieu = ( maximum + minimum ) / 2;
    if (minimum==maximum)
                          if (index==tableau[milieu])
                          return index; 
                          else return -1;
 
 
                          else
                          {
                               if (tableau[milieu]<=index){
 
                                                           return recherche(tableau,index,minimum+1,milieu);
 
 
                                                           }
                                                           else
                                                           {
 
                                                           return recherche(tableau,index,milieu,maximum);   
 
                                                           }; 
 
 
                          };
 
 
}
 
 
int main(){
    int tableau[100];
    tableau[0] = 1;
    printf("%d",tableau[0]);
 
    for(i=1;i<=99;i++){
                       tableau[i] = tableau[i-1] + i ;
                      printf(" - %d",tableau[i]); }
 
    printf("%d",recherche(tableau,150,0,99));                  
    scanf("%d",&i);
 
}

Merci beaucoup pour vos réponses c'est sympa ,)

Code:

1
2
3
 if (tableau[milieu]<=index) 
       return recherche(tableau,index,minimum+1,milieu); 
 else  return recherche(tableau,index,milieu,maximum);

Apparemment, le test est inversé

Code:

1
2
3
 if (tableau[milieu]>index) 
       return recherche(tableau,index,minimum+1,milieu); 
 else  return recherche(tableau,index,milieu,maximum);

La remarque de fearyourself est exacte au sujet de minimum+1.
Je crois que le code suivant devrait marcher :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
int recherche(int tableau[],int index,int minimum,int maximum)
{
  int milieu;
  if(tableau[minimum]==index) return minimum;
  if(tableau[maximum]==index) return maximum;
  if(tableau[minimum]>index || tableau[maximum]<index ) return -1;
  milieu = ( maximum + minimum ) / 2;
  if (tableau[milieu]>index)
        return recherche(tableau,index,minimum+1,milieu);
    else
        return recherche(tableau,index,milieu,maximum-1);
}