Oque é Busca Binária?
Imagine que você queira encontrar a página 132 de um livro com
350 páginas. Você não procuraria folha por folha desde a primeira
página, pois isso seria muito ineficiente. Em vez disso, abriria o livro
aproximadamente no meio e verificaria a página. Se ela fosse
175, você saberia imediatamente que a página procurada está antes
dela e continuaria procurando apenas nessa metade do livro.
O algoritmo de busca binária funciona de maneira semelhante.
Em vez de verificar cada elemento individualmente, ele divide o conjunto de
dados ao meio. Assim, metade dos elementos é descartada imediatamente,
restando apenas a metade que pode conter o valor procurado. Em seguida,
essa metade é dividida novamente, repetindo o processo até encontrar o
valor desejado.
Vamos ao exemplo. Como o livro possui 350 páginas, a primeira
divisão resulta em dois intervalos:
Em qual desses intervalos está a página 132? Exatamente, no
primeiro. Agora repetimos o processo: dividimos o intervalo de
0 a 175 ao meio, obtendo:
Como a página 132 está entre 88 e 175,
descartamos a primeira metade e repetimos o processo até que reste apenas
a página procurada.
Exemplo da Busca Binária
| Etapa |
Intervalo Atual |
Meio |
Comparação |
Próximo Intervalo |
| 1 |
0 – 350 |
175 |
132 < 175 |
0 – 175 |
| 2 |
0 – 175 |
87 |
132 > 87 |
88 – 175 |
| 3 |
88 – 175 |
131 |
132 > 131 |
132 – 175 |
| 4 |
132 – 175 |
153 |
132 < 153 |
132 – 152 |
| 5 |
132 – 152 |
142 |
132 < 142 |
132 – 141 |
| 6 |
132 – 141 |
136 |
132 < 136 |
132 – 135 |
| 7 |
132 – 135 |
133 |
132 < 133 |
132 – 132 |
| 8 |
132 – 132 |
132 |
Encontrado! |
Fim da busca |
Observe que foram necessárias apenas 8 comparações para
encontrar a página 132. Em uma busca sequencial, no pior caso, seria
necessário verificar até 350 páginas. Isso demonstra a
eficiência da busca binária: a cada comparação, metade das possibilidades
é descartada, reduzindo drasticamente a quantidade de elementos que ainda
precisam ser analisados.