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; | |
| } |
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; | |
| } |