#include <stdio.h>

struct studente {
   int matricola;
   char nome[30];
   char cognome[30];
} ;

#define MAX_STUDENTI  100

void print_elemento(struct studente elemento)
{
          printf("%8d %-30s %-30s\n",
                  elemento.matricola,
                  elemento.nome,
                  elemento.cognome);
}

void print_dati(int n, struct studente * array)
{
     int i;
        for (i = 0; i < n;i++) {
            print_elemento(array[i]);
        }
}

int inserimento(struct studente * array, int * n,
                struct studente nuovo_dato)
{
  if (*n < MAX_STUDENTI) {
    array[*n] = nuovo_dato;
    (*n)++;
    return 1;
  }
  else
    return 0;
}

int inserimento_ordinato(struct studente * array, int * n,
                         struct studente nuovo_dato)
{
  int i;
  if (*n < MAX_STUDENTI) {
    for (i = *n - 1; i >= 0; i--) {
      if (strcmp(array[i].cognome, nuovo_dato.cognome) > 0) {
        array[i+1] = array[i];
      }
      else {
        break;
      }
    }
    array[i+1] = nuovo_dato;
    (*n)++;
    return 1;
  }
  else
    return 0;
}

int find(struct studente * array, int n, char * cognome)
{
  int i;
  for (i = 0; i < n;i++) {
    if (strcmp(cognome, array[i].cognome) == 0)
      return i;
  }
  return -1; 
}

int binary_find(struct studente * array, int n, char * cognome)
{
   int low, high, mid;
   low = 0;
   high = n - 1;
   while (low <= high) {
     printf("Low: %d, High: %d\n", low, high);
     mid = (low + high) / 2;
     if (strcmp(array[mid].cognome, cognome) == 0)
       return mid;
     if (strcmp(array[mid].cognome, cognome) > 0)
       high = mid - 1;
     else
       low = mid + 1;
   }
   return -1;
}

int main(int argc, char **argv)
{
  struct studente dati[MAX_STUDENTI];
  int numero_dati = 0;
  for (;;) {
    int scelta, i, elem_trovato;
    struct studente temp;
    char cognome_da_cercare[30];
    printf("0- Fine\n");
    printf("1- Inserimento\n");
    printf("2- Stampa\n");
    printf("3- Ricerca\n");
    printf("4- Cancellazione\n");
    printf("Scegli la voce:");
    scanf("%d", &scelta);
    switch (scelta) {
      case 0:
        return 0;
      case 1:
        printf("Matricola:"); scanf("%d", &temp.matricola);
        printf("Nome:"); scanf("%s", temp.nome);
        printf("Cognome:"); scanf("%s", temp.cognome);
        if (inserimento_ordinato(dati, &numero_dati, temp) == 0)
          printf("Impossibile aggiungere un nuovo elemento\n");
        break;
      case 2:
        print_dati(numero_dati, dati);     
        break;
      case 3:
        printf("Inserisci il cognome:");
        scanf("%s", cognome_da_cercare);
        elem_trovato = binary_find(dati, numero_dati, cognome_da_cercare);
        if (elem_trovato == -1)
          printf("Elemento non trovato\n");
        else {
             print_elemento(dati[elem_trovato]);
        }
        break;
    }
  }
}