Um dos problemas mais frequentes no dia-a-dia é a procura de informação. Dependendo do tipo de pesquisa, nós vamos descobrindo e utilizando truques para agilizar esta pesquisa. Um exemplo da nossa infância é a procura de uma palavra no dicionário. Como é que nós procuramos o significado da palavra "inócuo" no dicionário?
Suponhamos que o dicionário tem 1000 páginas. Uma abordagem comum é abrirmos o dicionário no meio, 500ª página. Digamos que calhamos numa página cujas palavras começam por "L". Isto significa que "inócuo" tem de estar para a esquerda no dicionário pois "I" vem antes do "L".
Assim, podemos repetir o processo mas considerando apenas a primeira metade das páginas. Desta vez vamos à 250ª página e suponham que esta página tem palavras começam por "F". Deste modo, sabemos que "inócuo" tem de estar para a direita - iríamos para a 375ª página a seguir. Após repetir o processo, vamos encontrar (eventualmente) uma página referente à letra "I". De seguida, continuamos com a 2ª letra da palavra a procurar - "n" em "inócuo" - e assim sucessivamente até encontrar a palavra.
 |
| Exemplo da redução sucessiva do espaço de pesquisa numa pesquisa binária |
|
A procura no dicionário é provavelmente intuitiva para toda a gente e pode até parecer estranho sistematizar este processo. No entanto, é esta sistematização que nos permite aplicar este método num programa. No exemplo anterior, começamos com um dicionário de 1000 páginas e fomos reduzindo o intervalo de páginas a procurar (espaço de pesquisa) para metade em cada iteração: 1000 -> 500 -> 250 -> 125 -> 63 -> 32 -> 16 -> 8 -> 4 -> 2 -> 1. Reparem que necessitamos de procurar apenas 10 páginas em vez de 1000 para encontrar a palavra.
Este método tem o nome de
Pesquisa Binária (
Binary Search no TopCoder). Visto que reduzimos o espaço de pesquisa para metade em cada iteração, a complexidade temporal deste método é O(log N): log
2(1000) ~ 10. O único requisito da pesquisa binária é que exista uma ordem no
input, seja ele um dicionário (palavras ordenadas alfabeticamente), um
array de números ordenados ou outra.
Implementação em C++ da pesquisa de um número num
array ordenado de forma crescente (retorna o
índice no array:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| // Se existirem valores repetidos iguais a "valor", retorna um qualquer.
int PesquisaBinaria(int* valores, int n, int valor) {
int esq = 0, dir = n-1;
while (esq <= dir) {
int mid = (esq + dir) / 2;
if (valores[mid] == valor) { // encontrou!
return mid;
} else if (valores[mid] < valor) { // está na parte direita
esq = mid+1;
} else { // está na parte esquerda
dir = mid-1;
}
}
return -1; // inexistente
}
|
2 problemas relacionados já referidos em posts anteriores são:
- Procurar o menor número maior ou igual a um valor dado - função lower_bound em C++
- Procurar o menor número maior do que um valor dado - função upper_bound em C++
Este problema pode ser abordado com pesquisa binária. A diferença para a pesquisa binária tradicional é que não procuramos um número especifico. Não terminamos a pesquisa precocemente, mas encurtamos o espaço de pesquisa até 1 elemento.
Notem que a diferença entre as duas funções é apenas uma condição com < e outra com <=. Caso não exista solução, as funções devolvem n, o número de elementos do array.
No caso do LowerBound, se existirem múltiplos valores iguais ao valor a procurar, retorna o menor índice no array com esse valor.
1
2
3
4
5
6
7
8
9
10
11
12
13
| // Procura o menor número maior ou igual ao valor dado num array ordenado
int LowerBound(int* valores, int n, int valor) {
int esq = 0, dir = n-1;
while (esq <= dir) {
int mid = (esq + dir) / 2;
if (valores[mid] < valor) { // está na parte direita
esq = mid+1;
} else {
dir = mid-1;
}
}
return esq;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
| // Procura o menor número maior do que o valor dado num array ordenado
int UpperBound(int* valores, int n, int valor) {
int esq = 0, dir = n-1;
while (esq <= dir) {
int mid = (esq + dir) / 2;
if (valores[mid] <= valor) { // está na parte direita
esq = mid+1;
} else {
dir = mid-1;
}
}
return esq;
}
|
Existem outras aplicações da pesquisa binária. Por exemplo: como encontrar a raiz quadrada de um número sem recorrer a funções
standard?
