Busca Binária (Binary Search)

Definição

A Busca Binária (Binary Search) é um algoritmo eficiente para encontrar um elemento em uma lista ordenada. Em vez de percorrer todos os itens um por um (como na busca linear), ele divide a busca ao meio a cada passo, descartando metade dos elementos restantes.

O algoritmo compara o valor buscado com o valor do meio da lista:

Se forem iguais, o item foi encontrado.
Se for menor, a busca continua na metade inferior.
Se for maior, continua na metade superior.

Por que usar

A busca binária é ideal quando:

A lista está previamente ordenada;
Você precisa de buscas rápidas e frequentes;
Deseja reduzir o tempo de busca para grandes volumes de dados.

Complexidade

Melhor caso: O(1), se o elemento estiver exatamente no meio;
Pior caso: O(log n), pois a cada passo o espaço de busca é reduzido pela metade;
Espaço adicional: O(1) na versão iterativa; O(log n) na versão recursiva (por causa da pilha de chamadas).

Exemplo prático (Python)

def busca_binaria(lista, alvo):
    inicio = 0
    fim = len(lista) - 1

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

    return -1  # não encontrado

# Lista precisa estar ordenada
numeros = [1, 3, 6, 8, 10, 15, 20]
posicao = busca_binaria(numeros, 10)

if posicao != -1:
    print(f"Encontrado na posição: {posicao}")
else:
    print("Valor não encontrado.")

Saída

Encontrado na posição: 4