Pesquisa Binária - Parte 2: Fundamentos

No último post, falei um pouco sobre um método de pesquisa chamado Pesquisa Binária. Pegando na pesquisa num dicionário como exemplo, procurei demonstrar que nós próprios utilizamos este método intuitivamente. Enquanto que o outro post foi mais dedicado a código, neste post pretendo explorar um pouco os fundamentos que nos permitem usar este método de pesquisa.


A pesquisa binária assume que a resposta pretendida se encontra num dado intervalo [esquerda, direita] e descarta metade deste intervalo em cada iteração após analisar o ponto médio do intervalo. Para que isto seja possível, a resposta que procuramos deve seguir uma função crescente ou decrescente.

Para o exemplo da pesquisa de um número num array ordenado, esta função pode ser simplesmente 0 se o número no array for menor que o valor a pesquisar e 1 caso contrário.

Exemplo de pesquisa do valor 3 num array de inteiros

Visto desta forma, basta ir de encontro ao menor índice do array cuja função f(x) tem o valor 1 e verificar se o número nesse índice é igual ao valor a procurar. A chave é que o array está ordenado, assim ao analisar o ponto médio do intervalo, se este for maior que o valor a procurar, sabemos que todos os números para a direita também são maiores que o valor a procurar e podemos descartar essa metade do intervalo.

Outro exemplo de aplicação prática é como um método simples de descobrir o x tal que uma dada função tem um valor conhecido Y. Exemplo: descobrir a raíz quadrada de um número.
A raíz quadrada só existe em R caso Y ≥ 0. Assim, podemos usar a função f(x) = x², visto que esta função é crescente para x ≥ 0, como se pode ver na figura seguinte.

Gráfico da função f(x) = x², para x ≥ 0

É fácil cometermos o erro de pensar que a raíz quadrada está entre 0 e Y. Na verdade, a raíz quadrada para Y < 1 é maior que Y, e.g. √0.64 = 0.8. Assim, o limite superior da resposta é o maior valor entre 1 e Y.

Posto isto, a pesquisa binária é semelhante ao discutido no post anterior. Tomamos o valor médio do intervalo mid = (esquerda+direita) / 2. Se mid² > Y então mid é maior que o x pretendido e devemos descartar a metade superior do intervalo, caso contrário descartamos a metade inferior.

Por fim, quando estamos a lidar com números reais, é conveniente definir a precisão que pretendemos para a resposta, exemplo em C++:

1 2 3 4 5 6 7 8 9 10 11 12

double RaizQuadrada(double valor, double precisao) { double esquerda = 0.0, direita = max(1.0, valor); while (esquerda+precisao < direita) { double mid = (esquerda+direita) / 2.0; if (mid*mid > valor) { direita = mid; } else { esquerda = mid; } } return esquerda; }

Quando a amplitude do intervalo [esquerda, direita] não exceder a precisão pretendida, a pesquisa termina. A raíz de 14 é 3.7416573867(..) Exemplo de utilização da função anterior:

precisão 0.1       x = 3.71875000  erro absoluto 0.02290739
precisão 0.01      x = 3.73925781  erro absoluto 0.00239957
precisão 0.001     x = 3.74096680  erro absoluto 0.00069059

precisão 0.0001    x = 3.74160767  erro absoluto 0.00004972

precisão 0.00001   x = 3.74165440  erro absoluto 0.00000299

precisão 0.000001  x = 3.74165690  erro absoluto 0.00000049

precisão 0.0000001 x = 3.74165737  erro absoluto 0.00000002

Normalmente, a parte mais difícil é descobrir num dado problema que há uma função crescente/decrescente que podemos explorar com pesquisa binária.