Busca Binária -

Nesta aula aprenderemos sobre busca binária. Busca binária é o algoritmo de busca mais famoso na programação competitiva. Essa técnica é tão poderosa que se os nomes de pessoas do mundo estivessem escritos ordenados e você quisesse procurar por um nome específico você não demoraria mais do que 40 iterações.

Para que possamos usar busca binária, precisamos de um vetor ordenado.

Dado o seguinte problema: Temos um vetor ordenado com N elementos e temos Q perguntas, para cada pergunta é dado um valor X, seu programa deve responder “S” caso esse número esteja no vetor e “N” caso contrário.

A solução trivial seria para cada pergunta percorrer o vetor inteiro e checar para todas as posições se o valor nessa posição é igual a X ou não.

	#include <bits/stdc++.h>

	using namespace std;

	int N, Q, VETOR[100050], X;

	int main()
	{
	cin >> N >> Q;

	for(int i = 1; i <= N; i++) cin >> VETOR[i]; // Leio o vetor

	for(int i = 1; i <= Q; i++)
	{
	cin >> X; // Leio o nÃºmero que irei procurar

	bool achou = false;

	for(int j = 1; j <= N; j++) // procuro o nÃºmero no vetor
	{
	if(VETOR[j] == X) achou = true; // se ele existir, marco que achei o nÃºmero
	}

	if(achou) cout << "S\n"; // Se eu achei o nÃºmero, imprimo 'S'

	else cout <<; "N\n"; // Caso contrÃ¡rio, imprimo 'N'
	}

	return 0;
	}

view raw Busca_binaria_em_O(nÂ²).cpp hosted with ❤ by GitHub

No entanto essa solução é bem ineficiente, pois para cada perguntando fazemos O(N) operações, então a complexidade final do nosso programa ficará O(N*Q) o que é muito lento para N, Q ≤ 10⁵.

Uma solução muito mais eficiente seria da seguinte forma:

Estamos querendo saber se o valor X pertence ou não ao vetor, vale lembrar que o vetor está em ordem crescente, então se compararmos o valor X com o elemento na posição do meio do vetor conseguimos saber para qual metade do vetor o número X estaria:

Se X < vetor[meio], X está na primeira metade do vetor
Se X > vetor[meio], X está na segunda metade do vetor
Se X = vetor[meio], já sabemos que X está no vetor e o problema está resolvido

Dessa forma, observe que sempre descartamos metade do vetor para cada iteração, então o número de iterações não pode ser maior do que log₂ N. Então, para cada pergunta, conseguimos respondê-la em O(log₂ N) o que faz com que a complexidade final do nosso código fique O(Q*log₂ N).

	#include <bits/stdc++.h>

	using namespace std;

	int N, Q, VETOR[100050], X;

	int main()
	{
	cin >> N >> Q;

	for(int i = 1; i <= N; i++) cin >> VETOR[i];

	for(int i = 1; i <= Q; i++)
	{
	cin >> X;

	int ini = 1, fim = N, meio;

	bool achou = false;

	while(fim >= ini)
	{
	meio = (ini + fim)/2;

	if(X < VETOR[meio]) fim = meio - 1;

	if(X > VETOR[meio]) ini = meio + 1;

	if(X == VETOR[meio])
	{
	achou = true;

	break;
	}
	}

	if(achou) cout << "S\n";

	else cout << "N\n";
	}

	return 0;
	}

view raw Busca_binaria_em_O(Q*logâ‚‚ N).cpp hosted with ❤ by GitHub

Fale conosco!