/*
 *  BUSCABIN.C--Exemplo de Busca Binaria
 *  Problema: dada uma sequencia ordenada de N numeros reais 
 *  (tipo float)
 *  em ordem crescente, e um numero real X, verificar se X ocorre na
 *  sequencia.
 */
#include <stdio.h>
#define Nmax 100           /* Numero maximo de elementos em R[] */
int main(){
   int  N,   /* numero de elementos em R[] */
        i,
        Esq, /* indice do elemento mais aa esquerda
                no intervalo de busca em R[] */
        Dir; /* idem aa direita */
   float R[Nmax],  /* vetor de N elementos ja ordenados */
         X;        /* elemento a ser procurado em R[] */
   /*
    *  Leitura dos parametros
    */
   printf("\nDigitar o numero de elementos de R[] -> ");
   scanf("%d", &N);
   printf("\nN = %d\n", N);
   if(N>Nmax){
     printf("\nNumero maximo de elementos foi excedido\n");
     exit(0);
     } /*end if */
   printf("Digitar os elementos de R[] em ORDEM CRESCENTE -> ");
   for(i=0; i<N; i=i+1)
     scanf("%f", &R[i]);
   printf("\n");
   for(i=0; i<N; i=i+1){
     if(i!=0 && R[i-1] > R[i])
       printf("\nOs elementos de R[] nao estao em ordem crescente\n");
     printf("R[%d] = %f", i, R[i]);
     } /* end for i */
   printf("\nDigitar o elemento X a ser procurado em R[] -> ");
   scanf("%f", &X);
   printf("\nX = %f", X);
/* Busca Binaria de X em R[], em tempo proporcional 
    * a log N na base 2 */
   Esq= 0; Dir= N-1;
   i=(Esq+Dir)/2;    /* indice do elem. do "meio"de R[] */
   while(Esq <= Dir && R[i] != X){
     if(R[i]<X) Esq = i+1;
     else Dir = i-1;
     i=(Esq+Dir)/2;   /* novo indice do elem. do "meio"de R[] */
     } /* end while */
   /*
    *  Dar resposta final
    */
   if(R[i] == X)
     printf("\n--- X = %f ocorre em R[]\n", X);
   else
       printf("\n --- X = %f nao ocorre em R[]\n", X);
} /* end main */