Busca binária: aprenda a implementar em Python

Intordução

Já entendemos a importância da análise de complexidade de algoritmos para o desenvolvimento de softwares com um desempenho cada vez melhor. Então vamos pôr a mão na massa?

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

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()

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

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 = ["Brendo", "Erica", "Monica", "Nico", "Paulo", "Rodrigo", "Wanessa"]
    for i in range(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

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)
    inicio = 0
    fim=tamanho_da_lista-1

    while inicio<=fim:
        meio=(inicio+fim)//2
        if lista[meio] == nome_pesquisado:
            return meio
        elif lista[meio] < nome_pesquisado:
            inicio=meio+1
        elif lista[meio] > nome_pesquisado:
            fim = meio-1

    return -1

def main():
    lista_de_alunos = sorted(importa_lista('../data/lista_alunos'))
    for i in range(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á!