#include <stdio.h>
#define MAX 20 // abbiamo definito una costante MAX con valore 20


/*

4 2 7 9 14 15 5 0 1 8 17 19 20 22 23 i=dim-l

FI: 2 4 7 9 14 15 5 0 1 8 17 19 20 22 (23)  i= dim-2

F2: 2 4 7 9 14 5 0 1 8 15 17 19 20 (22) 23  i=dim-3

F3: 2 4 7 9 5 0 1 8 14  15  17 19 (20)  22  23  i=dim-4

F4: 2 4 7 5 0 1 8 9 14 15   17 (19) 20  22  23  i=dim-5

F5: 2 4 5 0 1 7 8 9 14 15   (17) 19 20  22  23  i=dim-6

F6: 2 4 0 1 5 7 8 9 14 (15) 17 19   20  22  23  i=dim-7

F7: 2 0 1 4 5 7 8 9 (14) 15 17 19 20 22 23  i=dim-8

F8: 0 1 2 4 5 7 8 (9) 14 15 17 19 20 22 23  i=dim-9

F9: 0 1 2 4 5 7 8 9 14 15 17 19 20 22 23

*/

/* PROTOTIPO DI FUNZIONE */

int lettura(int vettore[]);

void bubble_sort(int vett[], int dim);

int ricerca_binaria(int vettore[],int dim, int x);

int main()
{
    int i;
    // questi servono il riordinamento e la ricerca binaria
    int v1[MAX];
    int dim;
    int k;
    int pos; // indichera la posizione ricercata

    dim=lettura(v1);

    /* STAMPA IL VETTORE */
    /* cioe i=dim-1 */

    printf("\nVettore:\n");

    for(i=0; i<dim; i++)
    {
        printf("%d ", v1[i]);
    }

    /* all'interno del main richiamiamo il bubble_sort */

    bubble_sort(v1, dim);

    // ristampiamo il vettore ordinato
    printf("\n\nVettore Ordinato:\n");

    for(i=0; i<dim; i++)
    {
        printf("%d ", v1[i]);
    }

    printf("\n\nInserisci elemento da ricercare: ");
    scanf("%d", &k);

    pos=ricerca_binaria(v1, dim, k);

    if(pos!=-1) /// quindi se posizione e diverso da -1 allora l'elemento e stato trovato
        printf("\nElemento trovato in posizione %d\n", pos);

    else
        printf("\nElemento non trovato\n"); // perche vorra dire che pose=-1

    return 0;

}


/* DEFINIZIONE DI FUNZIONE  */

/* FUNZIONE DI LETTURA */

int lettura(int vettore[])
{
    int i=0;
    FILE *fp;

    fp=fopen("numeri.txt", "r");

    while(!feof(fp))
    {
        fscanf(fp, "%d", &vettore[i]);
        i++;
    }

    fclose(fp);

    return i; /* ritorna i che e il numero di elementi letti e inserendola
    nella dimensionedima allinterno del main che sarebbe  ** dim=lettura(v1); */
}

void bubble_sort(int vett[], int dim)
{
    int i, j, temp;

    for(i=dim-1; i>0; i--)
    {
        for(j=0; j<i; j++)
        {
            /** scambiando > con < otterremo un ordinamento in maniera decrescente cioe dal piu grande al piu piccolo **/
            if(vett[j]>vett[j+1]) // dobbiamo confrontare l'elemento di sinistra con l'elemento di destra
            {
                temp=vett[j];
                vett[j]=vett[j+1];
                vett[j+1]=temp;
            }
        }
    }
}

int ricerca_binaria(int vettore[],int dim, int x)
{
    int p;
    int u;
    int m;

    p=0; // p indica il primo elemento

    u=dim-1; // u indica l'ultimo elemento

    while(p<=u)
    {
        m=(p+u)/2;

        if(vettore[m]==x)
            return m;

        else if(vettore[m]<x)
            p=m+1;

        else
            u=m-1;
    }

    return -1; /* se la ricerca non ha dato nessun risultato si restituisce -1. perche se uscira fuori dal cilo
     while significa che p sara diventato maggiore di u, qindi l'elemento che stiamo cercando non e presente
     all'inteno del vettore */
}