Larback - Retornando conhecimento

A vida sem windows é vida.

Busca Binária em C++

A pesquisa ou busca binária (em inglês binary search algorithm ou binary chop) é um algoritmo de busca em vetores que segue o paradigma de divisão e conquista. Ela parte do pressuposto de que o vetor está ordenado e realiza sucessivas divisões do espaço de busca comparando o elemento buscado (chave) com o elemento no meio do vetor. Se o elemento do meio do vetor for a chave, a busca termina com sucesso. Caso contrário, se o elemento do meio vier antes do elemento buscado, então a busca continua na metade posterior do vetor. E finalmente, se o elemento do meio vier depois da chave, a busca continua na metade anterior do vetor.

#include <iostream>
using namespace std;
int buscaBinaria(int arranjo[],int tamanho, int chave) {
	// Na busca binária, espera-se que o vetor esteja ordenado
	 
	int i = 0;
	int f = tamanho -1;
	int meio;
	while (i<=f) {
		meio = (i+f)/2;
		if (arranjo[meio]==chave)
			return meio;
		else {
			if (chave>arranjo[meio])
				i=meio+1;
			else
				f=meio-1;
		}
	}
	return -1;
}
int main() {
	/* Programa principal
	*  Exemplo de utilização da função
	*/

	int v[] = {4,6,8,9,17,18,25,42,39,65};
	int tamanho = 10;
	int p,res;
	cout << "Qual valor a ser procurado?" << endl;
	cin >> p;
	res=buscaBinaria(v,tamanho,p);
	if (res==-1)
		cout << "O valor procurado não foi encontrado.";
	else
		cout << "O valor procurado encontra-se na posição " << res;
	return 0;

}