#include <iostream.h>
#include <conio.h>


void main()
{
	int v[100]; 	// vetor de 100 posições
	int n;	//tamanho da sequencia
	int i,k;	//contadores
	int men,meni;	//menor valor e seu indice
   int chave;
   int esq,dir,meio;

	//Lê e valida n (1<=n<=100)
	do
   {
		cout << "\nDIGITE O TAMANHO DA SEQUENCIA: ";
		cin >> n;
	}while(n<1||n>100);

	//Lê n inteiros
	for(i=0;i<n;i++)
	{
		cout << "ELEMENTO:  " << (i+1) << "\t";
		cin >> v[i];
	}
	//Ordena usando selection sort
	for(i=0;i<n-1;i++)
	{
		//Encontra o menor elemento entre v[i] e v[i-1]
		men=v[i];
		meni=i;
		for(k=(i+1);k<n;k++)
      {
			if(v[k]<men)
         {
				men=v[k];
				meni=k;
         }
		}
		//troca os elementos v[i] e v[meni] de posição
		v[meni]=v[i];
		v[i]=men;
	}
	//Imprime o vetor depois de ordenado
	for(i=0; i<n; i++)
		cout << "\nELEMENTO:  " << (i+1) << " =  " << v[i];
   //Consulta elementos enquando chave != 999
   cout << "\n\nDIGITE UM NUMERO A SER ENCONTRADO\nOU DIGITE 999 PARA ENCERRAR :\t";
   cin >> chave;
   while(chave!=999)
   {
   	// Procura usando busca binária
      esq=0;
      dir=n-1;
      meio=(esq+dir)/2;
		while(esq<=dir && chave!=v[meio])
		{
         if(chave<v[meio])
            dir=meio-1;
         else
            dir=meio+1;
         meio=(esq+dir)/2;
      }
      if(esq<=dir)
			cout << "ELEMENTO ENCONTRADO NA POSIÇÃO " << (meio+1) << "\n";
      else
      	cout << "ELEMENTO NÃO ENCONTRADO\n";
   	cout << "DIGITE UM NUMERO A SER ENCONTRADO\nOU DIGITE 999 PARA ENCERRAR :\t";
	   cin >> chave;
   }
	getch();
}