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!
