Técnicas de Programação 01 - Busca Binária

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 nm, 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 1n).

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 iniint 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 inimeio-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+1fim, 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:

Problemas para Praticar