/* File: ricbinri.c */
/* Time-stamp: "2001-05-25 15:06:34 calvanes" */
/* Scopo: ricerca in un vettore ordinato */

bool RicercaBinariaRic(int inf, int sup, TipoVettore A, TipoElemVettore elem,
                       int *posiz)
  /* Funzione ricorsiva che effettua la ricerca di elem nella parte di A
     compresa fra inf e sup. */
{
  int med;
  bool trovato;

  if (inf > sup)
    trovato = FALSE;          /* la parte del vettore tra inf e sup e` vuota */
  else {
    med = (inf + sup) / 2;
    if (elem == A[med]) {                     /* l'elemento e` stato trovato */
      *posiz = med;
      trovato = TRUE;
    }
    else
      if (elem < A[med])                      /* cerca nella parte inferiore */
        trovato = RicercaBinariaRic(inf, med-1, A, elem, posiz);
      else                                    /* cerca nella parte superiore */
        trovato = RicercaBinariaRic(med+1, sup, A, elem, posiz);
  }

  return trovato;
}  /* RicercaBinariaRic */


bool RicercaBinaria(TipoVettore A, TipoElemVettore elem, int n, int *posiz)
  /* Effettua la ricerca binaria di elem tra i primi n elementi di A, usando la
     ricorsione.  Il valore di ritorno e` TRUE se elem e` presente in A, FALSE
     altrimenti.  Se elem e` presente in A, posiz contiene l'indice della
     componente pari ad elem. */
{
  return RicercaBinariaRic(0, n-1, A, elem, posiz);
}  /* RicercaBinaria */