Aula por Rogério Júnior, Lúcio Figueiredo e Pedro Racchetti
Imagine o seguinte problema: dado um vetor ordenado de $$n$$ números distintos, faça um programa que responde a $$m$$ perguntas do tipo: “o número $$x$$ está no vetor?”. A primeira linha terá dois inteiros: os valores de $$n$$ e $$m$$, respectivamente. A segunda linha terá $$n$$ inteiros ordenados: os elementos do vetor. A terceira e última linha terá $$m$$ inteiros. Para cada um desses números, seu programa deve gerar uma linha na saída. Se o número não estiver no vetor, a linha deve ter o valor “-1”. Caso ele esteja, ela deve imprimir a posição do número no vetor (indexado de $$1$$ a $$n$$).
Tal problema parece ser bem simples: basta que percorramos o vetor inteiro com um for, procurado o número lido. Porém, percorrer o vetor tem complexidade $$O(n)$$, e esta operação será executada $$m$$ vezes, o que gera uma complexidade de $$O(n*m)$$. E se as únicas restrições do problema forem: $$1\leq n, m \leq 10^5$$? A complexidade será $$O(10^{10})$$, o que com certeza iria ultrapassar o tempo máximo de execução. Como fazer para verificar se um número está em um vetor ordenado de maneira mais eficiente?
Esse problema é semelhante a procurarmos uma palavra em um dicionário de $$n$$ páginas, supondo que basta achar a página. A primeira ideia que tivemos foi folhear, uma a uma, todas as páginas do dicionário, começando da primeira até a última, procurando a palavra. Nos piores casos, teremos que olhar todas as páginas do dicionário. Note que tal mecanismo de busca funcionaria com a mesma eficiência se as palavras do dicionário estivessem em ordem aleatória, ou seja, não estamos usando a nosso favor o fato de as palavras estarem ordenadas. Essa ordenação só nos trás uma vantagem: quando vemos que uma palavra não está em determinada página, sabemos, pela ordem alfabética, se ela, estando no dicionário, estará antes ou depois daquela página, o que elimina todas as outras opções. Assim, vamos tentar eliminar o máximo possível de páginas logo na primeira consulta ao dicionário: basta que o abramos bem no meio! Desse modo, se a palavra estiver lá, que bom que encontramos, se não, não importa se a palavra estará antes ou depois da página do meio, eliminarei metade das consultas que teria que fazer a cada uma das páginas da metade em que a palavra não se encontra. Agora, na metade que restou do dicionário, aplico o mesmo processo, até que só reste uma possibilidade de página em que a palavra pode estar: se ela lá estiver, achei a página, se não, ela não pode estar no dicionário!
E qual a complexidade desse algoritmo? Iremos repetir o processo de dividir o número de páginas possíveis ao meio até que reste somente uma página, logo, sendo $$c$$ o número de vezes que vou consultar o dicionário temos que: $$\frac{n}{2^c} = 1\Leftrightarrow n = 2^c\Leftrightarrow \log{n} = \log{2^c} = c \log{2} = c\Leftrightarrow c = \log{n}$$, logo a complexidade de uma busca é $$O(\log n)$$. Desse modo, realizando $$10^5$$ operações de complexidade $$O(\log{10^5})$$, teremos uma complexidade final de $$O(10^6)$$, o que certamente passa no tempo. Basta gora que implementemos a função que realiza essa busca eficiente no vetor, que é conhecida como busca binária.
Vamos declarar o array de inteiros de nome vetor, que guardará os inteiros ordenados. Agora, vamos declarar a função “int buscab(int x){}“, que irá retornar a posição de $$x$$ em vetor, ou -1 se ele não estiver no array. A função começará declarando três variáveis: int ini, int fim e int meio, que guardarão o começo, o fim e o meio do intervalo que vamos analisar, respectivamente. O valor inicial de ini será 1 e o de fim será $$n$$, pois no começo o número pode estar em qualquer posição do vetor. Ela terá um while que repetirá o algoritmo enquanto o intervalo tiver pelo menos um número (ini<=fim). A ideia é atribuir a meio o elemento mais ou menos na metade do intervalo (meio=(ini+fim)/2;) e verificar se o número do meio (vetor[meio]) é o que procuramos. Se ele for, retornamos o valor de meio. Se procuramos um número menor que o do meio, então agora devemos olhar, na próxima repetição do while, apenas para o intervalo compreendido entre ini e meio-1, pois é onde ele deve estar. Para isso, fazemos fim receber o valor meio-1. Se procuramos um número maior, olhamos, de maneira análoga, para o intervalo compreendido entre meio+1 e fim, com o comando “ini=meio+1;“. Se o while terminar e a função ainda não tiver retornado nada, então o número não está no vetor e retornamos o valor -1. Vale lembrar que os comando aqui usados só são corretos se o vetor estiver indexado de $$1$$ a $$n$$, correndo o risco de entrar em loop infinito caso haja a posição 0.
Segue o código que resolve o problema acima com a função buscab, para melhor entendimento:
Outro exemplo de busca binária: Lower Bound
Imagine o seguinte problema: É dado um vetor $$V$$ ordenado de $$n$$ inteiros e $$m$$ perguntas, cada uma consistindo de um inteiro $$x$$. Para cada pergunta, imprima o menor inteiro presente no vetor que é maior ou igual a $$x$$ (caso não exista nenhum, imprima $$-1$$).
Para resolver este problema, vamos utilizar uma busca binária bastante parecida com a do primeiro exemplo. Inicialmente, vamos definir os valores $$ini$$ e $$fim$$, ou seja, o intervalo da busca binária, como $$1$$ e $$n$$, respectivamente. Além disso, iremos definir uma váriavel $$ans$$ que será a resposta da pergunta encontrada pela busca, e assim, inicializaremos $$ans$$ com o valor $$-1$$.
Após isso, durante a busca binária (ou seja, enquanto $$ini \leq fim$$), vamos considerar o número na posição $$mid = \frac{ini+fim}{2}$$ do vetor; caso este valor seja maior ou igual a $$x$$, ele é uma “possível” resposta para a pergunta, porém, não necessariamente é o menor valor possível. Por isso, vamos atribuir o valor $$V[mid]$$ a $$ans$$ e reduziremos o intervalo da busca binária para $$[ini, mid-1]$$, ou seja, faremos $$fim = mid-1$$, já que qualquer possível resposta menor que $$V[mid]$$ está neste intervalo do vetor. Caso contrário, ou seja, caso $$V[mid] < x$$, o valor que chutamos na iteração atual da busca binária foi muito pequeno, e por isso, a resposta certamente estará na metade direita do vetor. Logo, neste caso faremos $$ini = mid+1$$ e realizaremos as próximas iterações da busca binária no intervalo $$[mid+1, r]$$.
Caso todos os valores no vetor sejam menores que $$x$$, a variável $$ans$$ continuará com seu valor inicial $$-1$$ durante toda a busca binária. Logo, ao fim do loop principal da busca binária, retornaremos a resposta do problema, $$ans$$. Assim, conseguimos responder cada pergunta com complexidade $$O(\log n)$$. Confira o código abaixo para melhor entendimento:
Nota: Vale lembrar que existe uma função do C++, lower_bound() que resolve o problema acima, ou seja, encontrar o menor número $$ \geq x$$ em um vetor ordenado. Além disso, a função do C++ upper_bound() encontra o primeiro elemento estritamente maior que $$x$$ em um vetor ordenado. Para mais informações sobre essas funções, clique aqui e aqui para encontrar suas páginas na referência do C++.
Busca Binária na resposta
Uma das aplicações mais importantes de busca binária é a de resolver certos tipos de problemas de minimização/maximazação. Para ilustrar este tipo de busca binária, vamos utilizar o problema Pão a Metro, da segunda fase da OBI 2008, Programação Nível 1.
Enunciado: Dados $$M$$ pães com comprimentos $$m_1, m_2, …, m_M$$, indique o maior tamanho possível de uma fatia tal que a soma da quantidade de fatias inteiras deste tamanho que conseguimos cortar de cada pão é maior ou igual a um número $$N$$. Por exemplo, se temos pães com comprimentos $$120, 89, 230$$ e $$177$$ e $$N = 10$$, o maior valor possível de uma fatia é $$57$$, já que podemos cortar duas fatias do primeiro pão (pois a divisão de $$120$$ por $$57$$ resulta em $$2$$ com resto $$6$$), uma fatia do segundo, quatro no terceiro e três no quarto, totalizando $$2+1+4+3 = 10$$ fatias.
Restrições:
- $$1 \leq N, M \leq 10^4$$
- $$1 \leq m_i \leq 10^4$$
Solução: Suponha que o tamanho de uma fatia é $$x$$. O que o problema pede é o menor valor de $$x$$ para que o somatório das partes inteiras das frações $$\frac{m_1}{x}, \frac{m_2}{x}, …, \frac{m_M}{x}$$ seja maior ou igual a $$N$$. Note que a medida que o valor $$x$$ aumenta, o somatório irá diminuir, já que valores maiores nos denominadores das frações irão torná-las menores. Logo, se o somatório das frações acima para um valor $$x$$ é maior ou igual a $$N$$, com certeza este valor será maior ou igual a $$N$$ também para qualquer $$y < x$$. Ou seja, sendo $$f(x) = \frac{m_1}{x} + \frac{m_2}{x} + … + \frac{m_M}{x}$$ (consideramos apenas as partes inteiras das frações), podemos afirmar que a função $$f(x)$$ é decrescente.
Esta observação é essencial para a resolução do problema. Vamos utilizar a busca binária para “chutar a resposta”, ou seja, iremos definir o intervalo em que a resposta pode se encontrar (intervalo $$[ini, fim]$$) e utilizar a propriedade de monotonicidade indicada no parágrafo acima para decidir para qual intervalo menor devemos reduzir nossa busca.
Note que o intervalo em que a resposta pode se encontrar é $$[1, 10^4]$$, já que a fatia possui tamanho maior ou igual a $$1$$ e se possuir tamanho maior do que $$10^4$$, a soma da quantidade de fatias em cada pão seria $$0$$. Logo, em cada iteração da busca binária, iremos testar se para $$x = mid$$ (onde $$mid$$ é igual a $$\frac{ini+fim}{2}$$) $$f(x)$$ é maior ou igual a $$N$$. Se sim, o valor $$mid$$ é uma possível resposta para o problema; porém, não sabemos se é a resposta máxima. No entanto, como a função $$f(x)$$ é decrescente, sabemos que a resposta do problema será $$mid$$ ou algum valor no intervalo $$[mid+1, fim]$$, pois queremos maximizar o tamanho da fatia. Se o caso contrário for verdade, ou seja, se $$f(mid) < N$$, o valor $$mid$$ chutado é muito alto, e por isso, reduziremos a nossa busca para o intervalo $$[ini, mid-1]$$.
Para testar se $$f(x)$$ é maior ou igual a $$N$$, podemos simplesmente utilizar uma função auxilixar que calcula $$ \frac{m_1}{x} + \frac{m_2}{x} + … + \frac{m_M}{x}$$ (onde consideramos apenas a parte inteira de cada fração) em $$O(M)$$. Assim, como em cada uma das $$O(\log 10^4)$$ iterações da busca binária realizaremos uma checagem em $$O(M)$$, a complexidade final da solução é $$O(M \cdot \log 10^4)$$.
Conira o código abaixo para melhor entendimento:
Exemplo de Busca Binária na resposta e Menor Caminho
Nota: O problema abaixo utiliza conceitos de grafos e menores caminhos. Por isso, é recomendado que você confira a sua solução apenas se já possui familiaridade com o assunto. Para aprender sobre caminhos mínimos, confira o material do Curso Noic.
Imagine o seguinte problema:
Você é o atual presidente da Nlogonia. Seu pais tem um sistema um tanto quanto interessante de estradas intermunicipais, que funciona da seguinte maneira:
- Existem $$N$$ cidades, numeradas de $$1$$ à $$N$$;
- Existem $$M$$ estradas;
- Cada estrada liga 2 cidades diferentes, e existem no máximo uma estrada que liga duas cidades;
- Toda estrada é bidirecional;
- Cada estrada tem um preço $$p$$ para ser usada;
- Cada estrada tem uma altura mínima $$h$$ para ser usada;
Como você se importa muito com os cidadãos da Nlogonia, você quer saber qual a altura mínima para ir da cidade $$1$$ à cidade $$N$$, com preço menor que $$K$$. Caso isso não seja possível, imprima $$-1$$.
Restrições: $$N, M \leq 10^5$$, e $$1 \leq p,h,k \leq 10^9$$
Solução:
Suponha que $$x$$ é a resposta do problema.
Podemos perceber que, como $$x$$ é a resposta, não existe $$i$$ tal que $$i \leq x$$ e que seja possível ir da cidade $$1$$ a cidade $$N$$ com preço total menor que $$K$$ passando apenas por estradas com altura mínimo máximo $$i$$.
Perceba também que, para qualquer $$x < j \leq max(h)$$, sendo $$max(h)$$ a maior altura mínima, é possível ir da cidade $$1$$ a cidade $$N$$, com preço total menor que $$K$$, passando apenas por estradas com altura mínimas menores que $$j$$, isso se deve ao fato que $$x$$ é menor que $$j$$, e como é possível fazer o caminho com estradas com altura mínimas de no máximo $$x$$, com certeza é possível fazer o caminho com no máximo $$j$$, já que podemos, pelo menos, usar as estradas no caminho com $$x$$. Logo, conseguimos encontrar uma propriedade de monotonicidade no problema.
Note finalmente que, se é possível fazer o percurso com preço total menor que $$K$$ com valor máximo de alturas mínimas nas estradas sendo $$x$$, com certeza o preço do caminho mais barato entre $$1$$ e $$N$$, usando apenas estradas com alturas mínimas menor que ou igual à $$x$$, é menor que $$K$$.
Utilizando os fatos apresentados acima, perceba que podemos usar uma busca binária para encontrar $$x$$. A nossa função de teste da busca consiste em checar se existe algum caminho de $$1$$ a $$N$$, passando apenas por estradas menores que $$x$$, com custo menor ou igual a $$K$$. Podemos encontrar esse caminho utilizando o algoritmo de Dijkstra, inserindo no grafo apenas arestas com altura $$h$$ menor ou igual a $$x$$. A complexidade final da solução é $$O(N \log^2 N)$$, já que em cada uma das $$O(\log N)$$ iterações da busca binária iremos utilizar o algoritmo de Dijkstra, que tem complexidade $$O(N log N)$$.
Segue o código, comentado, para melhor compreensão: