#include <stdio.h>

#define RECURSIVE   //da commentare o no a seconda se si vuole la versione ricorsiva o non

int i = 0;



/*****Versione non ricorsiva*****/

int cerca(int *v, int n, int x){
    int a = 0, b = n;
    while (a<b){
        int half = (a+b)/2;
        printf("iterazione %i, a = %i, b = %i, v[half = %i] = %i\n", i, a, b, half, v[half]);
        i++;
        if (v[half] == x) return 1;
        if (v[half] < x) a = half+1;
        else b = half;
    }
    return 0;
}

/*****End non rec*****/




/*****Versione ricorsiva*****/

int rec_cerca(int *v, int n, int x, int a, int b){
    if (a<b){
        printf("Sono nell'if\n");
        int half = (a+b)/2;
        printf("iterazione %i| a = %i| b = %i| v[half = %i] = %i\n", i, a, b, half, v[half]);
        i++;
        if(v[half] == x) return 1;
        if(v[half] < x) rec_cerca(v, n, x, half+1, b);
        else rec_cerca(v, n, x, a, half);
    }
    printf("Sono uscito dall'if\n");
    return 0;
}

/*****End rec*****/




int main(int argc, char* argv[]){
    int i;
    int *v = malloc(100*sizeof(int));
    int target = 57;
    for(i=0; i<100; i++){
        v[i] = 3*(i+1);
        printf("| %i ", v[i]);
    }
    printf("|\n");

    #ifdef RECURSIVE
    printf("Metodo ricorsivo\n");
    int res = rec_cerca(v, 100, target, 0, 100);
    #endif

    #ifndef RECURSIVE
    printf("Metodo NON ricorsivo\n");
    int res = cerca(v, 100, target);
    #endif

    printf("Valore di res = %i\n", res);
    if(res) printf("%i trovato!\n", target);
    else printf("%i non trovato!\n", target);
}