Newsgroup: it.comp.lang.c
Titolo: ricerca binaria

ehm, qualcuno potrebbe gentilmente dirmi dove ho sbagliato in questo
algoritmo?
/**//**//**//**//**//**//**//**//**//**//**//**//**/
#include<stdio.h>
#include<stdlib.h>
typedef enum{vero,falso} logical;
/**********************quasi sicuramente l'errore è qui, ma non riesco ad
individuarlo!!*********************/
logical bin_search(float *a,int n,float value)
{ logical trovato;
  int lower,upper,middle;
trovato=falso;
lower=0;
middle=n/2;
upper=n;
while(middle==0 || trovato==vero)
{ if( a[middle]==value)
  { trovato=vero;}
  else
  {if(a[middle]>value)
     { upper=middle;
       middle=(lower+upper)/2;}
   else
     { lower=middle;
        middle=(lower+upper)/2;}}}
return(trovato);
}
main()
{ float *a;
  int n,i;
  float value;
  logical ricerca;
printf("\t RICERCA BINARIA");
printf("\n inserire la grandezza dell'array\n ==>");
scanf("%d",&n);
a=(float*)malloc(n*sizeof(float));
printf("\n inserire ora gli elementi dell'array ordinato\n ");
for(i=0;i<n;i++)
{ scanf("%f",&a[i]);}
printf("\n inserire il valore che si vuole cercare nell'array\n ==>");
scanf("%f",&value);
ricerca=bin_search(a,n,value);
if(ricerca==vero)
{ printf("\n %.0f appartiene all'array\n",value);}
else if(ricerca==falso)
  { printf("\n %.0f non appartiene all'array\n",value);}
else
  { printf("huston abbiamo un problema\n");}
system("pause");
return(0);
}
/**/
quello che mi lascia dubbi è il fatto che l'output non è "huston abbiamo un
problema" (ovvero ricerca non vale nè 'vero' nè 'falso') ma bensì
"l'elemento tot non appartiene all'array" anche se vi appartiene
eccome!!!!!!!!!!!!!!!!!
ho provato a cambiare con
/**/ typedef enum{0,1}logical; /**/
ma il compilatore da zero errori ed 1 warning, è passato a 10-14 errori!!!
ciao a tutti

algoritmo?
Nel non usare bsearch(), che e' standard.

> Nel non usare bsearch(), che e' standard.
lo so, ma questo è uno degli algoritmi che devo preparare per l'esame di
programmazione.........
;-)

while(middle==0 || trovato==vero)
Perche' "trovato==vero" ? In questo modo se trovato diventa
vero tu dal loop non esci mai. Inoltre l'elemento che cerchi
potrebbe essere effettivamente il primo (quello di indice 0)
e in questo caso tu usciresti dal loop prima di averne
controllato il valore (e quindi prima di aver impostato
"trovato=vero" per segnalare il successo della ricerca).
C'e' molta gente che ha paura della ricerca dicotomica...
ed in effetti e' facile scrivere codice non corretto anche
in casi relativamente semplici come questo. Io ho trovato
che le cose diventano meno complicate da capire usando
questa rappresentazione mentale del problema:
   __ __ __ __ __
  |__|__|__|__|__|
  L              U
Lower e Upper li immagini come puntare *fra un elemento e
l'altro* e non ad un elemento. In questo modo diventa chiaro
quale e' il termine del loop di ricerca:
    while(lower<upper)
Infatti quando diventano uguali non e' presente piu' nessun
elemento su cui effettuare la ricerca. E in questo caso la
ricerca e' fallita.
middle lo calcoli come (lower+upper)/2 e middle effettivamente
punta ad un elemento... non fra elementi. Se hai trovato
l'elemento allora esci... altrimenti aggiusti lower=middle+1
oppure upper=middle. La ragione del "+1" diventa chiara se
ci pensi un momento... se a[middle] non e' il valore che
cerco allora voglio far puntare lower alla *destra*
dell'elemento puntato da middle... se invece devo cambiare
upper allora upper dovra' puntare alla *sinistra* dell'elemento
puntato da middle.
Il codice corretto diventa:
  logical bin_search(float *a,int n,float value)
  { 
    int lower=0,upper=n;
    while(lower<upper)
    {
      int middle=(lower+upper)/2;
      if (a[middle]==value)
        return vero;
      else if (a[middle]<value)
        lower=middle+1;
      else
        upper=middle;
    }
    return falso;
  }
HTH
Andrea
--
Andrea Griffini, Programmer
http://www.netservers.com/~agriff

 Andrea
grazie mille per l'aiuto