Atividade 4 - Estruturas de Dados I

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. Obs: suponha que os valores serão fornecidos pelo usuário já
ordenados.
#include <iostream>
using namespace std;
int buscaBinaria(int *vetor, int tamanho, int valor) {
int inicio = 0;
int fim = tamanho - 1;
while (inicio <= fim) {
int meio = inicio + (fim - inicio) / 2;
// Se o valor estiver no meio, retorna o índice
if (vetor[meio] == valor) {
return meio;
}
// Se o valor for menor, descarta a metade superior
else if (vetor[meio] > valor) {
fim = meio - 1;
}
// Se o valor for maior, descarta a metade inferior
else {
inicio = meio + 1;
}
}
// Se o valor não estiver no vetor, retorna -1
return -1;
}
int main() {
int n;
// Solicita o tamanho do vetor
cout << "Informe o tamanho do vetor: ";
cin >> n;
// Aloca o vetor
int *vetor = new int[n];
// Solicita os valores do vetor
cout << "Informe os valores ordenados do vetor:\n";
for (int i = 0; i < n; ++i) {
cin >> vetor[i];
}
int valorBusca;
// Solicita o valor
cout << "Informe o valor a ser buscado: ";
cin >> valorBusca;
// Realiza a busca binária
int resultado = buscaBinaria(vetor, n, valorBusca);
// Exibe o resultado
if (resultado != -1) {
cout << "O valor " << valorBusca << " foi encontrado no índice " << resultado <<
"." << endl;
} else {
cout << "O valor " << valorBusca << " nao foi encontrado no vetor." << endl;
}
// Libera a memória alocada
delete[] vetor;
return 0;
}