Busca binária: aprenda a implementar em Python | Alura Cursos Online
Busca binária: aprenda a implementar em Python
6 min6 minutos de leitura
6 min6 minutos de leitura
Autor(a)
Brendo Rodrigo Souza de Matos
Engenheiro de Software e professor universitário, especialista em Arquitetura de Software e Soluções, com experiência no desenvolvimento de sistemas distribuídos, microsserviços, computação em nuvem (AWS) e plataformas de alta escala. Atua na criação de soluções utilizando Java, Python e boas práticas de engenharia de software, sempre buscando unir fundamentos teóricos à aplicação prática.
Inscreva-se em nossa Newsletter
Fique por dentro de conteúdos, insights e oportunidades do universo tech. Receba novidades e lançamentos direto no seu e-mail.
No artigo mencionado acima apresentamos um problema de busca. que resolvemos através do algoritmo de busca binária. Ao final, deixamos um desafio a ser resolvido: que tal o implementarmos em Python?
Então vamos lá! Vamos desenvolver uma busca de estudantes para a Alura. Depois de achar a pessoa, nossa intenção é autenticá-la para autorizar o acesso à plataforma . Para isso, recebemos uma lista com todos os nomes de pessoas matriculadas.
Antes de tudo, vamos usar a busca linear
Decidimos, então, percorrer toda a lista em busca da pessoa a ser autenticada e chegamos à seguinte implementação:
from array import array
defbusca(lista, nome_pesquisado):
tamanho_da_lista = len(lista)
for atual inrange(0, tamanho_da_lista):
if (lista[atual] == nome_pesquisado):
return atual
return -1
def main():
lista_de_alunos = sorted(importa_lista('../data/lista_alunos'))
posicao_do_aluno = busca(lista_de_alunos, "Wanessa")
print("Aluno(a) {} está na posição {}".format(lista_de_alunos[posicao_do_aluno], posicao_do_aluno))
if name == "main":
main()
Perfeito! Desenvolvemos a função de busca com uma lista que contém 7 estudantes e também simulamos a busca com aproximadamente 85 mil, a quantidade aproximada de estudantes da Alura). Tudo funcionou bem e com desempenho aceitável, como mostra o algoritmo abaixo:
from array import array
def importa_lista(arquivo):
lista = []
with open(arquivo) as tf:
lines = tf.read().split('","')
for line in lines:
lista.append(line)
return lista
def busca(lista, nome_pesquisado):
tamanho_da_lista = len(lista)
for atual in range(0, tamanho_da_lista):
if (lista[atual] == nome_pesquisado):
return atual
return -1
def main():
lista_de_alunos = sorted(importa_lista('../data/lista_alunos'))
posicao_do_aluno = busca(lista_de_alunos, "Wanessa")
print("Aluno(a) {} está na posição {}".format(lista_de_alunos[posicao_do_aluno], posicao_do_aluno))
if name == "main":
main()
O grande problema!
Tudo executa adequadamente, mas vamos supor que o pessoal da equipe responsável pelo comercial entrou em contato conosco informando que fechamos novas parcerias com grandes empresas. Por isso, receberemos aproximadamente, 3000 autenticações de pessoas novas no próximo dia.
Sentindo preocupação com a qualidade do nosso serviço, decidimos fazer uma simulação simples para verificar como nossa busca reagiria a essa quantidade de requisições. E pensando no pior dos casos, vamos optar sempre pela busca da última pessoa da lista.
from array import array
defimporta_lista(arquivo):
lista = []
withopen(arquivo) as tf:
lines = tf.read().split('","')
for line in lines:
lista.append(line)
return lista
defbusca(lista, nome_pesquisado):
tamanho_da_lista = len(lista)
for atual inrange(0, tamanho_da_lista):
if (lista[atual] == nome_pesquisado):
return atual
return -1defmain():
lista_de_alunos = ["Brendo", "Erica", "Monica", "Nico", "Paulo", "Rodrigo", "Wanessa"]
for i inrange(0, 3500):
posicao_do_aluno = busca(lista_de_alunos, "Wanessa")
print("Aluno(a) {} está na posição {}".format(lista_de_alunos[posicao_do_aluno], posicao_do_aluno))
if __name__ == "__main__":
main()
Alteramos a chamada da busca e percorremos por um laço de repetição para simular, de forma descomplicada, as 3500 requisições de busca. Ao executar percebemos que demorou um tempo considerável.
Mas por que isso aconteceu?
Vamos fazer um cálculo simples para responder essa pergunta:
Para cada uma das 3500 requisições de busca, foram executadas 85 mil comparações, ou seja: (3500*85000) = 297500000 operações.
E caso a lista de pessoas ou de requisições cresça, o algoritmo crescerá de forma linear a estas quantidades. Então consideramos que cada um destes algoritmos são O(N) (Adiante falaremos mais sobre a notação big O neste artigo).
Agora vamos otimizar o algoritmo
Pensando nos alunos que iremos receber, vamos otimizar esse algoritmo utilizando a técnica de divisão e conquista usando a busca binária.
from array import array
defimporta_lista(arquivo):
lista = []
withopen(arquivo) as tf:
lines = tf.read().split('","')
for line in lines:
lista.append(line)
return lista
defbusca(lista, nome_pesquisado):
tamanho_da_lista = len(lista)
inicio = 0
fim=tamanho_da_lista-1while inicio<=fim:
meio=(inicio+fim)//2if lista[meio] == nome_pesquisado:
return meio
elif lista[meio] < nome_pesquisado:
inicio=meio+1elif lista[meio] > nome_pesquisado:
fim = meio-1return -1defmain():
lista_de_alunos = sorted(importa_lista('../data/lista_alunos'))
for i inrange(0,3500):
posicao_do_aluno = busca(lista_de_alunos, "Zeina")
print("Aluno(a) {} está na posição {}".format(lista_de_alunos[posicao_do_aluno], posicao_do_aluno))
if __name__ == "__main__":
main()
Antes de tudo, utilizamos a função sorted() do Python para retornar a lista em ordem alfabética. A partir disso começamos a buscar a aluna Zeina, que está no final da lista, para simular o pior caso.
Refatoramos a função busca para utilizar a busca binária, que consiste em comparar o valor pesquisado com o valor do item no meio da lista e caso sejam iguais, a posição do meio é retornada.
if lista[meio] == nome_pesquisado:
return meio
Caso o valor pesquisado seja antecedente ao do meio, o algoritmo descarta todos os valores posteriores.
elif lista[meio] > nome_pesquisado:
fim = meio-1
E caso o valor pesquisado seja posterior ao valor do meio, o algoritmo descarta todos os valores anteriores, até que sobre apenas o item desejado. Se o item restante não for o que queremos, será retornado um valor negativo.
elif lista[meio] < nome_pesquisado:
inicio=meio+1
Agora, ao realizar a simulação das 3500 requisições, percebemos que a execução é quase instantânea. E por que esse algoritmo executa tão rápido? Vamos calcular?
Comparando a eficiência dos algoritmos
Considerando, mais uma vez, que temos 85 mil estudantes e que a cada iteração de busca é descartada uma metade da lista em que não esteja aquele que buscamos, podemos calcular utilizando logaritmos na base 2 e concluir que a cada requisição da função busca, no pior caso, são executadas lg(N) operações, ou seja, lg(85000) ≃ 16 operações.
Mas ainda não acabou, visto que fizemos 3500 chamadas para essa função, portanto, executamos (3500 * 16) ≃ 56000 operações.
Assim, conseguimos otimizar o nosso algoritmo que antes executava quase 300 milhões de operações para apenas 56 mil. Dessa forma e assim, podemos ir mais seguros para a campanha que trará mais 3000 alunos para nossa plataforma!
Mais uma vez foi mostrada a importância de pensar em como nossos algoritmos irão se comportar de acordo com a quantidade de dados recebidos, e vale enfatizar que mesmo que haja abstrações de tais funções, como a função index() que realizaria essa busca com apenas uma chamada, é muito importante aprender esses fundamentos. Mas por que? Onde mais podemos aplicar isso?
Veja que para a solução da busca binária é necessário ter a lista ordenada, então utilizamos a função sorted() para executar tal tarefa. Mas imagine que a linguagem não nos oferecesse tal função? Como faríamos? Abordamos esse tema no artigo de ordenação em Python, nos vemos lá!
