Busca Binária
Aula Relacionada Recomendada:
Motivação
Pense no seguinte problema
Uma fábrica possui \(n \) máquinas que podem ser utilizadas para fabricar produtos. Seu objetivo é produzir um total de \(t \) produtos.
Para cada máquina, você sabe quantos segundos ela leva para fabricar um único produto. As máquinas podem trabalhar simultaneamente, e você pode definir livremente o cronograma de produção. Qual é o menor tempo necessário para produzir \(t \) produtos?
Nota
Tente resolver o problema antes de continuar a leitura.
Introdução
O conceito de busca binária surge quando buscamos encontrar valores em um determinado conjunto de forma rápida e eficiente.
Suponha que queiramos encontrar um elemento em um determinado array.
Uma abordagem genérica consiste em usar um laço for
e percorrer todos os seus elementos.
Uma possível implementação dessa busca é a seguinte:
search.cpp | |
---|---|
No entanto, há uma propriedade interessante: se os elementos do vetor estiverem ordenados, cada busca pode ser feita em \(O(\log{N}) \).
Na busca binária, escolhemos o elemento do meio do intervalo e, a cada iteração, decidimos se o próximo intervalo de busca ficará à direita ou à esquerda desse ponto, com base no valor do elemento que buscamos.
A ideia pode ser vizualizada a seguir:
A ideia apresentada anteriormente pode ser implementada da seguinte maneira:
Provando a complexidade
Busca Binária em Funções monótonas
Para além da simples busca de elementos, a técnica de busca binária pode ser aplicada na resolução de problemas de minimização e maximização.
Considere uma função booleana \(f(x) \). Em problemas desse tipo, queremos determinar o menor (ou maior) valor de \(x \) para o qual \(f(x) \) retorna verdadeiro. Para que isso seja possível de forma eficiente, é fundamental que \(f \) seja monótona. Sob essa condição, todos os pontos em que \(f(x) = true \) aparecem agrupados em um único intervalo contíguo.
Ou seja:
Para funções crescente, existe um ponto de corte \(x'\) tal que
Para funções decrescente, o padrão é análogo, mas com os valores invertidos:
Podemos usar essa propriedade para resolver o problema motivador.
Solução:
O objetivo é descobrir o menor tempo necessário para produzir uma quantidade \(t\) de produtos.
Podemos converter isso em um problema de minimização definindo uma função booleana
Para verificar se \(X\) segundos são suficientes, note que cada máquina \(i\) produz \(\lfloor X / a_i\rfloor\) produtos em \(X\) segundos (onde \(a_i\) é o tempo que a máquina \(i\) leva para fabricar um único produto).
Logo, o total produzido por \(n\) máquinas é
Monotonicidade
Para aplicar busca binária, é fundamental que \(f(X,t)\) seja monótona:
- Se \(f(x,t)=\mathtt{true}\), então \(f(y,t)=\mathtt{true}\) para todo \(y \ge x\).
- Se \(f(x,t)=\mathtt{false}\), então \(f(y,t)=\mathtt{false}\) para todo \(y \le x\).
Isso garante que existe um ponto de corte \(X'\) tal que
e podemos encontrá‑lo eficientemente por busca binária.
Exemplo
Caso de teste:
Ao atribuir valores de \(1\) a \(10\) à função \(f(X, t)\), observamos o seguinte comportamento:
O interessante é que podemos determinar o valor ótimo a partir de uma estimativa inicial, usando busca binária.
Algoritmo por busca binária
Suponha que sabemos que a resposta está em \([L, R]\). Então:
-
Calcule \( mid = \left\lfloor \frac{L + R}{2} \right\rfloor. \)
-
Avalie \(f(mid, t)\):
-
Se \(\mathtt{true}\), então toda solução \(\ge mid\) também é verdadeira \(\Rightarrow \) atualize \(R \leftarrow mid. \)
-
Se \(\mathtt{false}\), então toda solução \(\le mid\) também é falsa \(\Rightarrow \) atualize \(L \leftarrow mid + 1. \)
-
-
Repita até \(L = R\). Esse valor é o \(X'\) ótimo.
Simulação da busca binária (caso dado no exemplo):
A seguir, a tabela que mostra cada iteração com \(L\), \(R\),
\(mid = \big\lfloor (L+R)/2\big\rfloor\), o valor de \(f(mid,7)\) e a ação tomada:
Iteração | \(L\) | \(R\) | \(mid = \lfloor (L+R)/2\rfloor\) | \(f(mid,7)\) | Ação |
---|---|---|---|---|---|
1 | 0 | 20 | 10 | true | \(R \leftarrow 10\) |
2 | 0 | 10 | 5 | false | \(L \leftarrow 6\) |
3 | 6 | 10 | 8 | true | \(R \leftarrow 8\) |
4 | 6 | 8 | 7 | false | \(L \leftarrow 8\) |
5 | 8 | 8 | 8 | true | Fim: \(X' = 8\) |
Para aplicar essa abordagem, podemos considerar um limite superior maior para o intervalo, por exemplo \( [0,\,10^{18}] \), e implementar o algoritmo da seguinte forma:
Implementações do C++
O C++ possui algumas implementações de busca binária que são uteis em muitos problemas:
lower_bound
Dado um vetor ordenado, retorna um ponteiro para primeira posição maior ou igual a um valor \(X \) procurado.
Complexidade: \( O(\log{N})\)
Sintaxe:
Parametros:- first: Ponteiro pro primeiro elemento do range
- last: Ponteiro pro último elemento do range
- val: Valor a ser comparado.
Exemplo:
upper_bound
Dado um vetor ordenado, retorna um ponteiro para primeira posição estritamente maior a um valor \(X \) procurado.
Complexidade: \( O(\log{N})\)
Sintaxe:
Parametros:
- first: Ponteiro pro primeiro elemento do range
- last: Ponteiro pro último elemento do range
- val: Valor a ser comparado.
Exemplo:
Para mais detalhes sobre a implementação dessas funções: