/*************************************************************************
 *  Descricao: Algoritmo busca binaria iterativaem um vetor ordenado     *
 *  Compilador Utilizado: Borland C++ 3.1                                *
 *  Este codigo foi desenvolvido pelo Fundao da Computacao - UFMS        *
 *  www.fundao2000.cjb.net  &&  fundao2000@fundao2000.cjb.net            *
 *  Sugestao.: Este algoritmo pode ser facilmente alterado para palavras *
 *  em vetores de strigs (Ex.: Uma lista com varios nomes).              *
 *************************************************************************/
#include <iostream.h>
#include <conio.h>

int Busca_Bin(int[],int,int);

void main()
{
	int *A,t,i,x,p;
	clrscr();

	//Instrucoes para a construcao do vetor
	cout<<"\n\tBusca Binaria\n";
	cout<<"\n\tEntre com o tamanho do vetor: ";
	cin>>t;
	cout<<"\n\tEntre um vetor ordenado:\n";

	//Construcao do vetor
	A = new int[t];
	for(i=0;i<t;i++)
	{
		cout<<"\tA["<<i<<"] = ";
		cin>>A[i];
	}

	//Numero que deve ser encontrado no vetor
	cout<<"\n\tEntre com um numero que deve ser encontrado no vetor: ";
	cin>>x;

	//Realiza busca sequencial no vetor (retorna -1 se nao encontrar ou
	//a posicao do elemento no vetor)
	p = Busca_Bin(A,t,x);

	cout<<"\n\tO elemento "<<x<<" se encontra na posicao "<<p<<" do vetor.";

	getch();
}

//Procedimento da busca binaria iterativo
//Retorna -1 se o elemento nao esta no vetor ou a posicao do elemento no
//vetor caso contrario.
int Busca_Bin(int A[],int n,int x)
{
	int l,r,k,achou;

	l = 0;
	r = n-1;
	achou = 0;   //achou fica falso

	while( l<=r && !achou )
	{
		 k = (l+r)/2;         //pega o meio do vetor
		 if( x==A[k] )
			 achou = !achou;   //achou fica verdadeiro
		 else if( x<A[k] )
			 r = k-1;
		 else
			 l = k+1;
	}

	if( achou )
		return k;
	return -1;
}