terça-feira, 7 de janeiro de 2014

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): log2(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?

3 comentários: