Aula 11 - Busca Binária

0 Flares Facebook 0 0 Flares ×

Aula de Rogério Júnior

 

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 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).

Segue um exemplo de entrada e saída:

Entrada:

7 4

-2 0 4 7 8 9 11

5 -2 7 15

Saída:

-1

1

4

-1

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 1n, 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:

A implementação de uma busca binária é conhecida por ter pequenos bugs que quase nunca identificamos, o que a faria entrar em algum loop infinito. Enfim, o código aqui mostrado funciona bem, mas, caso você esqueça algum detalhe, algumas pessoas gostam de colocar um contador dentro do loop que impede que o número de repetições do while passe de 35, por exemplo, visto que o log do maior valor que cabe em um int é 32, evitando o loop infinito.

Vale notar também que a ideia da busca binária não se restringe somente a sequências crescentes, mas a qualquer intervalo em que, buscando determinado elemento, olho para alguma posição do intervalo e sei se ele está antes ou se está depois de tal posição. Certa vez me deparei com um problema em que parte dele consistia em identificar, em O(\log{n}), o maior elemento de um vetor de inteiros positivos que crescia até certo elemento, que era o máximo, e a partir de então começava a decrescer. Segue um exemplo de vetor assim, de 7 elementos:

1 3 4 5 6 4 3

É fácil ver que o elemento é o procurado (o máximo) se o anterior a ele for menor ou igual que ele e o posterior for menor. No caso, 6 é antecedido de 5 e sucedido por 4. Vamos aplicar a busca binária: checar se o número do meio é o maior é checar se seu antecessor é menor que ele e seu sucessor também ("if(vetor[meio-1]<vetor[meio] && vetor[meior+1]<vetor[meio])"). Se isso ocorrer, retornamos o valor salvo em "vetor[meio]". Note que para a função não dar problema no começo e no fim do vetor, as posições 0 e n+1 devem estar declaradas (n é o número de elementos), e guardarem o inteiro 0, pois ele é menor que todos os elementos do vetor, não quebrando, portanto, sua lógica de ser crescente e depois decrescente, mas nunca serão acessados pela busca binária. Caso o número do meio não seja o maior, olhamos se seu sucessor é menor que ele. Se for, então já estamos na parte do vetor que decresce, e devemos olhar apenas para a metade atrás da posição meio ("if(vetor[meio+1]<vetor[meio]) fim=meio-1;"). Se o sucessor for maior, então ainda estamos na parte que cresce, e devemos olhar a metade depois da posição meio ("if(vetor[meio+1]>vetor[meio]) ini=meio+1;"). Segue a implementação dessa busca binária:

Note que, em alguns problemas podemos usar a busca binária em um vetor ordenado com números de 1 a n para chutarmos a sua resposta (n é a resposta máxima) e depois testarmos se ela é válida. Imagine que queremos um inteiro resp mínimo que resolve o problema e todos os outros maiores que ele também resolvem, mas buscamos o menor. Suponha também que testar um número como resposta leva tempo O(n). Se fôssemos testar um por um todos os números, do menor para o maior, a complexidade seria n*O(n) = O(n²). Mas se usarmos a busca binária para procurarmos a resposta, buscando o primeiro número que funciona, só usaríamos log n consultas, o que daria uma complexidade de O(n \log{n}).

O código seria bem simples: testo se o número do meio do intervalo funciona. Se ele funcionar, o guardo em alguma variável, e procuro um menor que ele que também funcione, com busca binária, olhando agora para a metade do intervalo que está antes do meio. Se o número não funcionar, então a resposta é maior que ele e devo procurar a na metade do intervalo que vem depois do meio. Segue, para exemplo, a implementação de uma busca binária que encontra, em log n, o primeiro número de um vetor ordenado int vetor[100100], que é maior ou igual a um int x.

Agora que você já sabe de tudo isso, tente fazer os problemas abaixo. Se não conseguir fazer algum problema, ou tiver alguma dúvida sobre a teoria apresentada, clique aqui para voltar à página inicial do curso e preencher o formulário para nos enviar sua dúvida!

Problema 1 - Ogros - OBI F1P2

Problema 2 - The Playboy Chimp

Problema 3 - Pão a Metro

Problema 4 - Binary Search (Lembre-se que aqui pode haver repetição de números, e você quer a primeira aparição de alguém. Logo, achar o número não é o suficiente, você deve verificar se ele é o primeiro dentre as aparições do número procurado. Se não for, a primeira aparição estará antes ou depois dele?)

Problema 5 - Tartarugas

Problema 6 - Agressive cows


As aulas do Curso Noic de Informática são propriedade do Noic e qualquer reprodução sem autorização prévia é terminantemente proibida. Se você tem interesse em reproduzir algum material do Curso Noic de Informática para poder ministrar aulas, você pode nos contatar por esta seção de contato para que possamos fornecer materiais específicos para reprodução.

0 Flares Facebook 0 0 Flares ×
0 Flares Facebook 0 0 Flares ×
%d bloggers like this: