//	Programa sobre pesquisa bin ria
//	Adriano Marto Reis
//	05/01/2000

#include <conio.h>
#include <stdio.h>

/*     Os valores INICIO e FIM  sÆo definidos aqui porque
   este ‚  um programa  para  fins  did ticos  e  sabemos
   previamente quantos  dados derÆo guardados.  Em  casos
   reais, estes valores devem ser definidos dinamicamente.
*/
#define	ERRO	-1
#define	INICIO	0
#define	FIM	9
const int Tabela [] = { 3, 4, 8, 12, 13, 15, 17, 21, 23, 30 };

/*	Esta fun‡Æo procura a chave passa por parƒmetro
   no vetor Tabela. Se achar, retorna a ¡ndice da chave
   se nÆo retorna ERRO. O vetor todo nÆo ‚ passado  por
   parƒmetro porque esta ‚ uma fun‡Æo recursiva e  isso
   exigiria muito da pilha interna do computador.
*/
int ProcuraChave (int Chave, int Inicio, int Fim)
{
	int Meio;
	Meio = (Inicio + Fim) / 2;

	// se encontrar a chave...
	if (Tabela [Meio] == Chave) return Meio;
	// se nÆo encontrar a chave...
	if (Inicio == Fim) return ERRO;
	// se a chave estiver na primeira metade...
	if (Chave < Tabela [Meio]) return ProcuraChave (Chave, Inicio, Meio - 1);
	// se a chave estiver na segunda metade...
	if (Tabela [Meio] < Chave) return ProcuraChave (Chave, Meio + 1, Fim);

	return ERRO;
}

//**************************************************************************

void main (void)
{
	int Chave, Indice;

	clrscr ();
	printf ("Digite o valor a ser procurado: ");
	scanf ("%d", &Chave);
	Indice = ProcuraChave (Chave, INICIO, FIM);
	if (Indice != ERRO)
		printf ("Esta chave est  na posi‡Æo %d da tabela.", Indice);
	else
		printf ("Esta chave nÆo se encontra no vetor.");
	getch ();
}