atividade_04

Prévia do material em texto

ESTRUTURA DE DADOS I
ATIVIDADES DA AULA 04
Faça um programa na linguagem C/C++ que implemente o método de Busca Binária. O programa deverá conter um vetor alocado dinamicamente de tamanho n, onde n deverá ser fornecido pelo usuário. A seguir, o programa deverá solicitar ao usuário que informe os n valores para o vetor. Feito isso, o programa também deverá pedir para que o usuário informe o valor a ser buscado. Por fim, o programa deverá mostrar na tela o resultado da busca. 
#include <iostream>
using namespace std;
int buscaBinaria(int x, int n, int v[]){
 int left, middle, right;
 left = 0;
 right = n-1;
 while(left < right){
 middle = (left + right)/2;
 if(v[middle] == x)
 return v[middle];
 else
 {
 if(v[middle] < x)
 left = middle + 1;
 else
 right = middle - 1;
 }
 }
 return v[right];
}
int main()
{
 int n, busca;
 cout<<"\nInforme a quantidade de posicoes do vetor: ";
 cin>>n;
 int* vetor = new int[n];
 cout<<"\nInnforme os valores das posicoes: "<<endl;
 for(int i=0;i<n;i++){
 cout<<"Posicao "<<i<<": ";
 cin>>vetor[i];
 }
 cout<<"\nPor fim digite o valor a ser encontrado: ";
 cin>>busca;
 if(buscaBinaria(busca,n,vetor) == busca){
 cout <<"\nEncontramos o valor informado."<<endl;
 }else{
 cout <<"\nNao encontramos este valor informado."<<endl;
 }
 return 0;
}