#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<conio.h>


void ordina(int vett[],int n);
void bsrc_i(int vett[],int n,int x);
int bsrc_r(int vett[], int l, int r,int x);
void main()
{
	int n,i,vett[100],valore,scelta,indice,x;
   char stream[6],sky[6];
   printf("Inserisci il numero di elementi del vettore: ");
   gets(stream);
   n=atoi(stream);
   for(i=0;i<n;i++)
   {
   	printf("inserisci il %d valore: ",i+1);
      gets(stream);
      valore=atoi(stream);
      vett[i]=valore;
   }
	ordina(vett,n);
   do{
      printf("\n[1]ricerca iterativa\n[2]ricerca ricorsiva\n-->");
      gets(sky);
      scelta=atoi(sky);
      if(scelta==0) continue;
      printf("Inserisci il valore da trovare: ");
   	gets(stream);
   	x=atoi(stream);
   	switch(scelta){
   	case 1: 	bsrc_i(vett,n,x);
            	break;
   	case 2:	indice=bsrc_r(vett, 0,n,x);
      			if(indice!=-1)
               	printf("Elemento cercato e' in posizione :%d ",indice+1);
   				break;
      }
      }while(scelta!=0);
}

void ordina(int vett[],int n)
{
	int i,j,temp;
   for(j=n-1;j>0;j--)
   	for(i=0;i<j;i++)
         if(vett[i]>vett[i+1])
         {
         	temp=vett[i];
            vett[i]=vett[i+1];
            vett[i+1]=temp;
         }
}
void bsrc_i(int vett[],int n,int x)
{
	int l,r,m,trovato=0;
   char stream[6];

   l=0;
   r=n;
   while(l<r && trovato==0)
   {
      printf("%d %d \n",l,r);
   	m=(l+r)/2;
   	if(x==vett[m])
   	{
   		printf("%d",m+1);
      	trovato=1;
   	}
   	else
      {
   		if(x<vett[m])
      		r=m-1;
      	else
      		l=m+1;
   	}
   }
   if(!trovato)
   	printf("elemento non trovato");
   getch();
}
int bsrc_r(int vett[], int l, int r,int x)
{
	int m;
   if(l>r) return(-1);
   else{
   	m=(l+r)/2;
      return(x==vett[m]? m: x<vett[m]? bsrc_r(vett,l,m-1,x): bsrc_r(vett,m+1,r,x));
      }
}