Pesquisa binária vs Pesquisa simples

Se você é um desenvolvedor (a) que busca entender e melhorar seu código, é fundamental entender os fundamentos de algoritmos.

Você já se perguntou como funciona as funções que lidam com array como o filter, map, findIndex, find e tantas outras do Javascript ou da sua linguagem favorita?

Nesse artigo aprenderemos sobre a diferença entre a pesquisa simples e uma pesquisa binária (em arrays ordenados), vamos lá!

Pesquisa simples

Eis um exemplo prático de como funciona a pesquisa simples. Vamos supor que o seu chefe te pede para encontrar um relatório em uma pasta, porém a mesma está ordenadas em ordem crescente de acordo com o nome do cliente, você precisa pesquisar pelo relatório número 84, usando a ideia de pesquisa simples você iria abrir a caixa, começando pelo documento de número 1 e leria documento por documento até encontrar o que seu chefe pediu, horrível neh?! Supondo que você tivesse 128 documentos, você teria que no pior dos casos ler todos os documentos (log(n) aprenderemos a como calcular o tempo de execução de um algoritmo mais pela frente então já se inscreve no canal), vamos levar em consideração que para cada documento lido você gasta 30 segundos, tempo de abrir a pasta do mesmo, ler e identificar o número do arquivo. Você levaria 3840 segundos (1 hora e 4 minutos) caso o relatório fosse o último da lista ou seja DESPERDIÇARIA BASTANTE TEMPO!

Pesquisa binária (Uma maneira mais eficiente de buscar)

Vamos usar o exemplo acima, porém dessa vez como sabemos que os arquivos estão ordenados em ordem crescente, utilizaremos a pesquisa binária. Você como um ser pensante e alfabetizado sabe que o número 84 está mais para o final dos arquivos existentes, com isso em mente decide começar a buscar da metade para a frente ou seja, já eliminou 50% dos documentos, considerando que a lista tinha 128 documentos, agora já são apenas 64 documentos ([64, 65, ..., 127, 128]), analisando novamente, consegue determinar que o arquivo de número 84 está na primeira metade dos documentos restantes e corta a mesma pela metade outra vez, a lista de documentos ordenados agora ficou com apenas 32 docs ou seja, caiu pela metade novamente, mais uma vez você decide cortar pela metade a lista para poder analisar e assim sucessivamente até chegar ao arquivo de número 84 que é aonde você encontrará o arquivo para seu chefe, ta ok mas o quão isso foi vantajoso você deve estar se perguntando, vamos calcular:

Levando em consideração que você teria 128 documentos a serem analisadas, e a cada ação tomada você eliminava metade dos mesmos, podemos calcular a velocidade da pesquisa utilizando uma função simples que você provavelmente odiava no ensino médio assim como eu, vejamos:

log 128   ->   2 elevado a X = 128   ->   128 == 2 elevado a 7

Ou seja no pior dos casos você teria que tomar apenas 7 ações para identificar o documento, pois cada vez que você analisava conseguia cortar pela metade o número de possibilidades, vamos agora calcular quantos segundos você levaria para identificar esse arquivo que lhe foi solicitado:

7 x 30 (número de segundos para cada leitura conforme o exemplo da lista simples), você levaria apenas 210 segundos (3 minutos e 30 segundos) para identificar esse arquivo, uma diferença absurda de mais de UMA HORA PARA A PESQUISA SIMPLES, agora você deve conseguir imaginar o quão isso é poderoso.

No próximo arquivo aprenderemos sobre notação Big O para aprendermos a cálcular a velocidade de nossos algoritmos, se increve ai!