A Mágica Da Pesquisa Binária
Você já parou para entender como pesquisa binária funciona dentro do código e conceitualmente e como te ajuda a resolver certos problemas de programação?
A pesquisa binária é uma técnica poderosa para encontrar elementos em conjuntos de dados ordenados.
Sua eficiência reside na capacidade de reduzir pela metade o número de elementos a serem pesquisados a cada iteração, o que a torna especialmente útil para conjuntos de dados extensos.
A compreensão do funcionamento da pesquisa binária é fundamental para qualquer pessoa envolvida com algoritmos e estruturas de dados, pois é uma ferramenta essencial para resolver uma variedade de problemas de forma eficiente e elegante.
Aprimorando a eficiência de buscas 👀
Pense num login de um sistema, em grande parque deles precisamos colocar e-mail de senha.
Quando desenvolvi esse tipo de feature (mesmo sem saber) realizei pesquisa binária, pois preciso realizar um busca no banco de dado que seja eficiente, em grande parte a pesquisa binária entra nesse caso com um banco relacional. (em grande parte, não em todas)
Como que funciona a grosso modo:
Preparação dos dados
Primeiro, os dados dos usuários, incluindo seus e-mails, são armazenados em um banco de dados relacional, como o MySQL ou PostgreSQL. Para garantir a eficiência da pesquisa binária, os dados devem estar ordenados por e-mail na tabela do banco de dados.
Início da pesquisa
Quando um usuário tenta fazer login inserindo seu e-mail, o sistema inicia a pesquisa binária. O sistema verifica o e-mail fornecido pelo usuário com o e-mail armazenado no meio da lista. Se o e-mail do usuário for igual ao e-mail no meio da lista, o sistema confirma a correspondência e permite o login.
Redução do intervalo de busca
Se o e-mail do usuário for menor do que o e-mail no meio da lista, o sistema descarta a metade superior da lista, pois sabe que o e-mail do usuário só pode estar na metade inferior. Da mesma forma, se o e-mail do usuário for maior, a metade inferior é descartada. Esse processo de redução do intervalo de busca pela metade é repetido até que o e-mail do usuário seja encontrado ou até que não haja mais elementos para verificar.
Eficiência da pesquisa
A pesquisa binária é altamente eficiente, pois reduz pela metade o número de elementos a serem verificados a cada iteração. Isso é especialmente útil em grandes bancos de dados, onde a pesquisa linear (percorrer cada registro sequencialmente) seria muito mais lenta.
Retorno do resultado:
Uma vez que o e-mail do usuário é encontrado com sucesso na pesquisa binária, o sistema pode recuperar outras informações associadas a esse usuário, como senha ou informações de perfil, e permitir o login bem-sucedido na rede social.
Assim, a pesquisa binária em um login de rede social em um banco de dados relacional permite uma busca eficiente pelo e-mail do usuário (dependendo da volumetria desses dados), garantindo uma experiência de login rápida e sem problemas para os usuários da plataforma.
Uma pesquisa burra 🤡
Dado o fluxo abaixo:
Basicamente eu quero que meu sistema advinhe o número de 1 a 100 que estou pensando.
A ideia de uma pesquisa meio burra é começar com o menor número e ir gradativamente aumentando até chegar no 100…
Pensando em memória de sistema isso é extremamente burro pois eu preciso alocar muito espaço de memória para uma busca que deveria ser simples
Uma busca um pouco melhor
Você poderia também começar a busca pelo maior número, no caso comecei pelo 60, continua sendo o número baixo com o que eu quero que você advinhe, porém você á eliminou mais da metade nos números!
Mas ainda sim ir voce vai ir eliminando metade por metade pode levar um tempo até achar o número que eu quero que você ache, no caso se você chutar 70, já te digo que o número é alto…
Com a pesquisa binária, você chuta um número intermediário e elimina metade dos números restantes a cada vez que for dando sua sugestão!
O próximo número a seguir a pesquisa pra adivnhar o número que estou pensando seria… 65, o número intermediário entre 60 e 70
Mas ainda sim não é o número que estou pensando….
Porém se você for um pouco mais perto… 63!!!!
YEEEEEES
Isso é pesquisa bináriaaaaaa!
Quando eu aprendi isso fiquei maluca, é super simples!
Pesquisa binária te elimida várias etapas de pesquisa!
Evoluindo nosso software que dei de exemplo no início, suponhando uma busca com mais de 240.00 usuários, na pior das hipóteses teríamos 240.00 etapas na pesquisa simples até achar o usuário no banco de dados.
Com a pesquisa bonparia teremos apenas 18 etapadas, diminuindo o esforço da nossa query e otimizando a pesquisa do nosso banco nesse caso.
Lembrando que a pesquisa binária só funciona se a ista for ordenada!
Transformando em código
No código abaixo vou usar pesquisa binária para advinhar o numero de um array ordenado, no caso querendo fazer uma advinhação de um número alto:
A complexidade do tempo do algoritmo de pesquisa binária é O(log n), onde n é o número de elementos na lista.
Isso ocorre porque, a cada iteração do loop, o intervalo de busca é reduzido pela metade. Como a lista é dividida ao meio em cada iteração, o número de iterações necessárias para encontrar o elemento desejado cresce logaritmicamente com o tamanho da lista.
Portanto, o algoritmo de pesquisa binária é altamente eficiente, especialmente para grandes conjuntos de dados, pois o tempo de execução cresce de forma muito mais lenta do que o número de elementos na lista.
Não faz ideia do que é complexidade de tempo do algoritmo? Comenta aqui que esse pode ser o próximo tema que eu posso mostrar aqui 😜
Finalizamos a news de hoje com um overview basicão de pesquisa binária pra você manjar de como usar nos desafios do leetcode da vida, ou também pra quem sabe brincar com ele num projeto que esteja fazendo pra entender seu funcionamento!
Dica de ouro 💖
Tá, você se interessou pelo conteúdo e quer entender mais?
Infelizmente ainda não abriu vagas pra nova turma do JS Expert, porém vou indicar um curso incrível do Erick para você que quer usar testes automatizados a seu favor:
MÉTODO DE TESTES AUTOMATIZADOS COM JAVASCRIPT
A gente só sabe o valor de bons conteúdos quando passamos por perrengues reais e nenhum link da internet ajuda a gente, rs
Então fica a dica de estudo pra você!
Dicas da semana 🔥
[INGLÊS] - Inglês descomplicado com 47% de desconto! Conheçam a plataforma que eu estudo e pratico inglês → FLUENCYPASS
[EVENTO] - Evento gratuito da NodeBR em São Paulo com o tema de Devs que Criaram Startups!!! Será insano dia 08 de Maio → https://guild.host/events/devs-que-criaram-startups-yam0rp
Playlist da semana
Playlist do meu treino de musculação hahaha: