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];
 
	for(int i = 1; i <= Q; i++)
	{
		cin >> X;
 
		bool achou = false;
 
		for(int j = 1; j <= N; j++)
		{
			if(VETOR[j] == X) achou = true;
		}
 
		if(achou) cout << "S\n";
 
		else cout <<; "N\n";
    }
	
	return 0;
}

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:

  1. Se X < vetor[meio], X está na primeira metade do vetor
  2. Se X > vetor[meio], X está na segunda metade do vetor
  3. 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;
}