Precisamos Falar Sobre Algoritmos: Pesquisa Binária

A pesquisa binária é um dos muitos algoritmos de busca, ele recebe como entrada uma lista ordenada de elementos e o elemento que desejamos buscar, se o elemento buscado estiver na lista, recebemos como resposta a posição que aquele elemento se encontra, caso contrário a pesquisa retorna None. É preciso lembrar que pesquisa binária só funciona se a lista estiver ordenada, isso é necessário pois o elemento é buscado de forma ordenada dentro da lista. ex: temos uma lista de elementos dentro de um array [1,2,3,4,5,6,7,8,9,10] e queremos saber se o elemento 8 faz parte da lista, a primeira coisa que o algoritmo faz é partir a lista ao meio e verificar se o elemento é maior ou menor do que o elemento do meio, que seria 5 e no nosso exemplo ele seria maior então todos os elementos para trás seriam ignorados e a busca continuaria do numero 6 em diante.

Implementação de um algoritmo de busca binária usando Python

def pesquisa_binaria(lista, elemento):
    esquerda = 0
    direita = len(lista) - 1
    while esquerda <= direita:
        meio = (esquerda + direita) // 2
        chute = lista[meio]
        if chute == elemento:
            return meio
        elif chute > elemento:
            direita = meio - 1
        else:
            esquerda = meio + 1
    return None