Aula por Rogério Júnior, Lúcio Figueiredo e Pedro Racchetti
Imagine o seguinte problema: dado um vetor ordenado de números distintos, faça um programa que responde a perguntas do tipo: "o número está no vetor?". A primeira linha terá dois inteiros: os valores de e , respectivamente. A segunda linha terá inteiros ordenados: os elementos do vetor. A terceira e última linha terá 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 a ).
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 , e esta operação será executada vezes, o que gera uma complexidade de . E se as únicas restrições do problema forem: ? A complexidade será , 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 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 o número de vezes que vou consultar o dicionário temos que: , logo a complexidade de uma busca é . Desse modo, realizando operações de complexidade , teremos uma complexidade final de , 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 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á , 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 a , 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 ordenado de inteiros e perguntas, cada uma consistindo de um inteiro . Para cada pergunta, imprima o menor inteiro presente no vetor que é maior ou igual a (caso não exista nenhum, imprima ).
Para resolver este problema, vamos utilizar uma busca binária bastante parecida com a do primeiro exemplo. Inicialmente, vamos definir os valores e , ou seja, o intervalo da busca binária, como e , respectivamente. Além disso, iremos definir uma váriavel que será a resposta da pergunta encontrada pela busca, e assim, inicializaremos com o valor .
Após isso, durante a busca binária (ou seja, enquanto ), vamos considerar o número na posição do vetor; caso este valor seja maior ou igual a , ele é uma "possível" resposta para a pergunta, porém, não necessariamente é o menor valor possível. Por isso, vamos atribuir o valor a e reduziremos o intervalo da busca binária para , ou seja, faremos , já que qualquer possível resposta menor que está neste intervalo do vetor. Caso contrário, ou seja, caso , 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 e realizaremos as próximas iterações da busca binária no intervalo .
Caso todos os valores no vetor sejam menores que , a variável continuará com seu valor inicial durante toda a busca binária. Logo, ao fim do loop principal da busca binária, retornaremos a resposta do problema, . Assim, conseguimos responder cada pergunta com complexidade . 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 em um vetor ordenado. Além disso, a função do C++ upper_bound() encontra o primeiro elemento estritamente maior que 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 pães com comprimentos , 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 . Por exemplo, se temos pães com comprimentos e e , o maior valor possível de uma fatia é , já que podemos cortar duas fatias do primeiro pão (pois a divisão de por resulta em com resto ), uma fatia do segundo, quatro no terceiro e três no quarto, totalizando fatias.
Restrições:
Solução: Suponha que o tamanho de uma fatia é . O que o problema pede é o menor valor de para que o somatório das partes inteiras das frações seja maior ou igual a . Note que a medida que o valor 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 é maior ou igual a , com certeza este valor será maior ou igual a também para qualquer . Ou seja, sendo (consideramos apenas as partes inteiras das frações), podemos afirmar que a função é 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 ) 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 é , já que a fatia possui tamanho maior ou igual a e se possuir tamanho maior do que , a soma da quantidade de fatias em cada pão seria . Logo, em cada iteração da busca binária, iremos testar se para (onde é igual a ) é maior ou igual a . Se sim, o valor é uma possível resposta para o problema; porém, não sabemos se é a resposta máxima. No entanto, como a função é decrescente, sabemos que a resposta do problema será ou algum valor no intervalo , pois queremos maximizar o tamanho da fatia. Se o caso contrário for verdade, ou seja, se , o valor chutado é muito alto, e por isso, reduziremos a nossa busca para o intervalo .
Para testar se é maior ou igual a , podemos simplesmente utilizar uma função auxilixar que calcula (onde consideramos apenas a parte inteira de cada fração) em . Assim, como em cada uma das iterações da busca binária realizaremos uma checagem em , a complexidade final da solução é .
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 cidades, numeradas de à ;
- Existem 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 para ser usada;
- Cada estrada tem uma altura mínima 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 à cidade , com preço menor que . Caso isso não seja possível, imprima .
Restrições: , e
Solução:
Suponha que é a resposta do problema.
Podemos perceber que, como é a resposta, não existe tal que e que seja possível ir da cidade a cidade com preço total menor que passando apenas por estradas com altura mínimo máximo .
Perceba também que, para qualquer , sendo a maior altura mínima, é possível ir da cidade a cidade , com preço total menor que , passando apenas por estradas com altura mínimas menores que , isso se deve ao fato que é menor que , e como é possível fazer o caminho com estradas com altura mínimas de no máximo , com certeza é possível fazer o caminho com no máximo , já que podemos, pelo menos, usar as estradas no caminho com . Logo, conseguimos encontrar uma propriedade de monotonicidade no problema.
Note finalmente que, se é possível fazer o percurso com preço total menor que com valor máximo de alturas mínimas nas estradas sendo , com certeza o preço do caminho mais barato entre e , usando apenas estradas com alturas mínimas menor que ou igual à , é menor que .
Utilizando os fatos apresentados acima, perceba que podemos usar uma busca binária para encontrar . A nossa função de teste da busca consiste em checar se existe algum caminho de a , passando apenas por estradas menores que , com custo menor ou igual a . Podemos encontrar esse caminho utilizando o algoritmo de Dijkstra, inserindo no grafo apenas arestas com altura menor ou igual a . A complexidade final da solução é , já que em cada uma das iterações da busca binária iremos utilizar o algoritmo de Dijkstra, que tem complexidade .
Segue o código, comentado, para melhor compreensão: