#include<iostream.h>
#include<stdlib.h>

// costanti
#define NUM 30000
#define NON_TROVATO -1

// prototipi funzioni
void init_array(long*);
void stampa_array(long*);
void stampa_risultato(int);
int sequential_search(long *, int, int, int);
int binary_search(long *, int, int, int);


int main(){
 long valori_ordinati[NUM];
 long valore_da_cercare;
 int pos;
 

 // inizializza il vettore con valori ordinati ma
 // pseudocasuali
 init_array(valori_ordinati);
 //stampa_array(valori_ordinati);

 while(1){
   cout << "Inserisci un valore da ricercare (0 per uscire): ";
   cin >> valore_da_cercare;
   if(valore_da_cercare<=0)
     break;

   cout << "Ricerca sequenziale: ";
   pos=sequential_search(valori_ordinati, valore_da_cercare,0,NUM-1);
   stampa_risultato(pos);

   cout << "Ricerca binaria: ";
   pos=binary_search(valori_ordinati, valore_da_cercare,0,NUM-1);
   stampa_risultato(pos);
  }

  return 0;
}

void init_array(long *a){
 for(int ii=0; ii<NUM; ++ii)
   a[ii]=10*ii+rand()%10;
}

// solo per debug
void stampa_array(long *a){
 for(int ii=0; ii<NUM; ++ii)
   cout << ii << "->" << a[ii] << " ";
 cout << endl;
}

void stampa_risultato(int p){
   if(p!=NON_TROVATO)
    cout << "trovato in " << p << endl;
   else
    cout << "valore non trovato" << endl;
}

//scandisce l'array fino a che non trova il valore
int sequential_search(long *a, int v, int l, int r){
 register int ii;

 for(ii=l;ii<=r;++ii)
  if(a[ii]==v) return ii;
 return NON_TROVATO;
}

// dato che l'array e' ordinato lo partiziono
// fino a trovare il valore
int binary_search(long *a, int v, int l, int r){
 while(r>=l){
   int m=(l+r)/2;
   if(v==a[m])
     return m;
   if(v<a[m])
     r=m-1;
   else
     l=m+1;
  }
 return NON_TROVATO;
}