Cap. 1 — Pesquisa binária.

O que é pesquisa binária?

Pesquisa binária é um algoritmo muito comum, usado para solucionar problemas de busca de elementos em uma lista, como buscar um nome no Facebook ou em uma lista telefônica.

Em sua entrada precisamos de uma lista ordenada e o alvo.

Pesquisa simples

Uma maneira muito comum de resolver esse problema é com a pesquisa simples, nela percorremos a lista toda em busca de um alvo… contudo a pesquisa simples ela leva muito empo para executar.

Exemplo imagine que você está tentando adivinhar um número em uma lista de 1 até 100, a pesquisa simples nesse caso seria chutar os números de um por um, assim, 1,2,3,4,5,6….99 e 100, no pior caso, temos 99 tentativas para um acerto, por isso temos a pesquisa binária

<aside> 📢 Notação big O = O(N)

</aside>

def pesquisa_simples(lista, alvo):
    for index, num in enumerate(lista, start=0):
        if num == alvo:
            return index
    return None

lista = range(100)

print(pesquisa_simples(lista, 100))

Pesquisa Binária

A pesquisa binária é muito mais rápida, com ela chutamos um número intermediário e eliminamos a metade dos números restante a cada vez, por exemplo, chutar 50, 75, 63.. até chegar no número alvo, perceba que esse método é muito mais rápido do que a pesquisa simples. A pesquisa binária, portanto, consiste em eliminar a metade dos números a cada tentativa

<aside> 📢 Notação big O = O(log n)

</aside>

Código de Pesquisa binária

def pesquisa_binaria(lista, item):
    baixo = 0
    alto = len(lista) - 1
    while baixo <= alto:
        meio = (baixo + alto) // 2
        chute = lista[meio]
        if chute == item:
            return meio
        if chute > item:
            alto = meio - 1
        else:
            baixo = meio + 1
    return None

minha_lista = [1, 3, 5, 7, 9]
print(pesquisa_binaria(minha_lista, 3))

Cap. 2 — Ordenação por seleção.