Busca Binária

Hoje vamos falar um pouco mais sobre algoritmos, que são as bases da computação. Especificamente sobre um tipo de busca que eu já utilizei em um projeto e nunca imaginei que iria utilizar, a busca binária.

Os algoritmos de busca inicialmente parecem teóricos demais, mas, na verdade, podemos usar bastante em projetos. Há algum tempo, antes de termos o Android e IOS, era comum termos os Palmtops, eles tinham memória péssima e precisávamos fazer uma busca que nem era tão grande (essa busca demorava demais de forma sequencial) a partir disso, assumimos uma restrição nos dados, deixando-os ordenados para a busca binária e assim conseguimos resolver o problema.

Vou dar um exemplo de um problema com um vetor de 5 itens. Deixávamos o vetor de forma sequencial e salvavamos esses slots de dados sequencialmente, mas isolados, com isso era possível saber que quando fossemos naquele ponto de memória, teria poucas iterações.

A estratégia era a seguinte: tentamos acertar primeiro o item do meio, por exemplo, o número 3, se o número 3 é igual ao número que eu estou buscando, ele é retornado, caso eu esteja procurando o 2 por exemplo, eu sei que ele é menor que o 3, então meu próximo espaço de busca será 1 ou 2, com isso é tentado de novo, se acertar, ele retorna, caso contrário tentará de novo e por aí vai.

Por esse motivo é chamado de busca binária, porque sempre vamos dividir em dois espaços. O pior dos casos é ele dividir todos pela metade. Vamos implementar agora:

const vetor = [1, 2, 3, 4, 5]

const binSearch = (vetor, left, right, valor) => {

if (right >= left){

const indice =  parseInt(left + (right-left)/2)

if(vetor[indice] === valor){

return valor

}

if(vetor[indice] > valor){

return binSearch(vetor, left, indice-1, valor)

}

return binSearch(vetor, indice+1, right, valor)

}

return -1

}

console.log(binSearch(vetor, 0, vetor.length-1, 20))

console.log(binSearch(vetor, 0, vetor.length-1, 5))

Para saber se o algoritmo acabou, uma das maneiras é se por algum motivo o item do lado direito for maior que do lado esquerdo, é válido, já que vamos marcar os lados para acertar a metade, caso ele não encontre do lado esquerdo, vamos procurar do lado direito, e por fim retornar -1 caso não encontrarmos em nenhum dos lados.

Nos casos, fizemos um valor que não existe, 20, e um que existe, 5. A vantagem que tirei nesse projeto é que toda vez que acessavamos o índice sempre gastava muito tempo, então poderíamos fazer o  seguinte para economizar:

const binSearch = (vetor, left, right, valor) => {

if (right >= left){

const indice =  parseInt(left + (right-left)/2)

const  atual = vetor[indice]

if(atual === valor){

return valor

}

if(atual > valor){

return binSearch(vetor, left, indice-1, valor)

}

A medida que escalamos, isso vai ficando cada vez mais interessante já que aumentamos muito o número de itens e o número de vezes que ele passa é pequeno.

Curta o DevPleno no Facebookinscreva-se no canal e cadastre seu e-mail para não perder nenhuma novidade. Deixe suas dúvidas e sugestões nos comentários. Abraço!