ALGORITMO DE BUSCA BINARIA

Em algoritmo, a pesquisa binária, também conhecida como pesquisa de vetores, pesquisa logarítmica ou divisão binária, é um algoritmo de pesquisa que encontra a posição de um valor alvo dentro de uma matriz. A pesquisa binária compara o valor de destino com o elemento do meio da matriz. Se não forem iguais, a metade em que o alvo não pode estar é eliminada e a busca continua na metade restante, novamente tomando o elemento do meio para comparar com o valor escolhido na busca, e repetindo isso até que o valor alvo seja encontrado. Se a pesquisa terminar com a metade restante vazia, o alvo não está na matriz/vetor.

A pesquisa binária é mais rápida que a pesquisa linear, exceto para matrizes pequenas. No entanto, a matriz deve ser classificada primeiro para poder aplicar a pesquisa binária. Existem estruturas de dados especializadas projetadas para pesquisa rápida, como tabelas de hash, que podem ser pesquisadas com mais eficiência do que a pesquisa binária. No entanto, a pesquisa binária pode ser usada para resolver uma gama mais ampla de problemas.  

ALGORITMO

A pesquisa binária funciona em arrays/listas definidas. A pesquisa binária começa comparando um elemento no meio da lista com o valor escolhido. Se o valor de destino corresponder ao elemento, sua posição na matriz será retornada. Se o valor de destino for menor que o elemento, a pesquisa continua na metade inferior da matriz. Se o valor de destino for maior que o elemento, a pesquisa continua na metade superior da matriz. Ao fazer isso, o algoritmo elimina a metade em que o valor alvo não pode estar em cada iteração, tornando muito mais rápido.

A seguir um exemplo em busca binaria em Kotlin:

A busca binaria diminui drasticamente o tempo de varredura de um elemento dentro de um vetor. Se hipoteticamente eu queira encontrar um número 100 dentro de um vetor com números de 1 a 100, se eu usar uma busca linear simples, eu teria que varrer um numero um por um até chegar ao número 100. A princípio poderia encontrar bem rápido o número em um vetor desse tamanho, agora imagina quanto tempo demoraria para encontrar um vetor de 1 milhão de números? Muito tempo, correto?

A busca binaria usa o conceito de logaritmo na base 2 (LOG2), onde encontrando a sua potência seria o resultado de etapas que a busca binaria encontraria o número alvo do vetor. 

Vamos a um exemplo:

O tamanho do vetor são 100 números e precisamos encontrar o número 100 (último número), precisaremos encontrar o log da base 2 que levando a sua potência o resultado seja dentro de um raio de resultados igual ou superior a 100. 

2⁷ = 2 elevado a 7 potência = 128

Ou seja, o log 2 = 128. e igual a log 2⁷ = 128.

O Resultado de etapas para encontrar o número 100 seria "7" na busca binaria. 

Quantas etapas seriam necessárias para encontrar o número de 1.000.000 dentro do vetor com essa quantidade de números? 

Encontrando a potência do log2 que de um resultado dentro do raio de 1 milhão de números. 

O resultado para encontrar o elemento seria 20, porque 2 elevado a 20 = 1.048.576,00

Se você optar pela busca linear simples, você precisaria de exatos 1 milhão de etapas para encontrar o resultado! 

A busca binaria é um algoritmo poderoso para deixar a estrutura muito mais fluida e rápida, podendo ser usada em diferentes situações.

Bibliografia:

Aditya, Y. Bhargava. Título: Entendendo Algoritmos: Um guia ilustrado para programadores e outros curiosos. Primeira Edição. Brasil, publicação traduzida em português: Editora Novatec, abril 2017.