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 $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:

Problemas para Praticar

• Ogros - OBI F1P2 2008
• The Playboy Chimp
• Pão a Metro - OBI F2P1 2007
• Binary Search
• Tartarugas
• Agressive cows
• Array Division