A parte vari smanacciamenti mi sono accorto che faceva casino perchè invece di un array di char nt l'avevo passato come un array di int alla funzione di ricerca ed ovviamente mi prendeva caratteri a razzo.

Ora l'ho riaggiustata un pochino (anche perchè vedendo che non andava l'avevo pastrocchiata molto, ed è la seguente:

codice:
//Funzione di ricerca binaria
int ricerca_lineare(char nt[], char cercato)
{
    int i=0;
    int ritorno = 0;//in caso di elemento non trovato
    while((nt[i] != cercato) && (nt[i] != NULL))
    {
        i++;            
    }    
    if(nt[i] == cercato)
    {
         ritorno = 1;        
    }
    return ritorno;
}
//funzione per la ricerca di un nt non utilizzato
char trova_nt_libero(char nt1[])
{
     int i,j;
     char ritorno = 'A';
     int return_ricerca = -1;
     i=0;
     //finchè ci sono simboli non terminali
     while(nt1[i] != NULL)
     {
        do
        {
            //cerca se l'attuale lettera dell'alfabeto contenuta in ritorno è utilizzata
            return_ricerca = ricerca_lineare(nt1,ritorno);  
            if(return_ricerca == 1)
            {
                //se è già utilizzata passa alla prosisma lettera
                ritorno++;                  
            }       
        }while(return_ricerca == 1);
        //prosegue finchè non si trova una lettera non utilizzata           
        i++;
     }
      nt1[i] = ritorno;
      nt1[i+1] = NULL;
      return ritorno;               
}
Voi dite che è ancora incasinata?