1 de novembro de 2010

Busca Binária

Olá!

Hoje vamos ver um problema clássico na computação. A busca em um vetor ordenado.
Imagine o problema:

Dado um inteiro x e um vetor v[0 ... n - 1] crescente, encontrar um indice k tal que v[k] == x

Quando fiz um post sobre vetores, descrevi um algoritmo trivial para resolver esse problema. Você pode vê-lo aqui.
O que temos que nos perguntar é: "Tem alguma forma de encontrar o indice que queremos sem precisar comparar x com todos os elementos de v?". E a resposta é: Sim, pequeno padawan.
Para resolver o problema vamos utilizar a busca binária.

Vamos ilustrar essa técnica?
Imagine que você tenha um dicionário na mão e eu peço para você me dar a definição da palavra zootecnia.
Qual característica do dicionário é importantíssima para buscarmos alguma palavra nele?
Ele é ordenado alfabeticamente.
Então o que fazemos? Rasgamos ele no meio, tendo na mão agora dois dicionários menores. Verificamos se a palavra está na página do meio do rasgo. Se sim, pronto, achamos a palavra. Se não, precisamos procurar mais.
Sabemos que a letra Z não está na primeira metade, por isso jogamos ela fora. Então, pegamos a metade que sobrou e rasgamos no meio novamente. De novo vemos se a palavra está na folha do meio. Não? Então pergunte: A letra procurada está na primeira metade? Não, então jogamos fora e ficamos com a outra metade. Mais uma vez rasgamos no meio essa metade, e repetimos o processo. Fazendo isso, um momento acontecerá de sobrar uma página do dicionário, onde estará a letra e a palavra que você procura. E se a palavra não estiver no dicionário, você vai rasgar tudo até sobrar uma folha só, e ela não vai estar lá. E você não precisou comparar sua palavra com todas do dicionário pra descobrir alguma informação.

Isso é a busca binária!
Se queremos encontrar um inteiro x em um vetor crescente v, precisamos apenas dividir ele em dois, depois novamente em dois, depois novamente, até que a divisão sobre apenas x - ou, se não estiver no vetor, retorne -1.

Mas como implementar?
Poderíamos implementar tanto uma função iterativa quanto uma função recursiva. Hoje vamos de iterativa :)
Algoritmo de Busca Binária em C

Explicando o algoritmo:
Nós ficamos em um laço de repetição, que repete enquanto o limite inferior for menor ou igual ao limite superior. Ou seja, se eu tenho um vetor v[0 ... n - 1], ele primeiro tem limInf = 0 e limSup = n - 1. Então dividimos no meio: meio = (limInf + limSup) / 2.
Se x já estiver na posição do meio, retornamos x. Se não, nós fazemos a seguinte pergunta: "x é maior do que o elemento do meio?" Se sim, ele está na metade maior, então pegamos nosso limInf e atribuimos limInf = meio + 1. Se não, ele está na metade menor, e o que fazemos é atribuir o limSup = meio - 1.
Caso na primeira divisão o elemento x esteja na metade menor, nossos limites serão limInf = 0 e limSup = meio - 1.
Então, caso as divisões ocorram e nenhum k satisfaça v[k] == x, o algoritmo retorna -1.

Pronto! Esse é o algoritmo de busca binária - solução iterativa :)

Até a próxima!