Pesquisa Binária

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₂(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?