DEV Community

Cover image for 🔍 Desvendando a Pesquisa Binária em Python: Um Guia para Quem Está Começando
Cláudio Filipe Lima Rapôso
Cláudio Filipe Lima Rapôso

Posted on

🔍 Desvendando a Pesquisa Binária em Python: Um Guia para Quem Está Começando

#phyton #algorithms #programming #webdev

Você já tentou procurar uma palavra em um dicionário físico? 📖 Se sim, provavelmente não começou pela primeira página. Em vez disso, você foi direto para o meio, viu em que letra estava, e então ajustou sua busca para frente ou para trás. Parabéns! Sem saber, você já usou o princípio da pesquisa binária.

Neste artigo, vamos explorar esse algoritmo de forma bem tranquila, como se estivéssemos conversando. Vamos entender o que ele faz, por que é tão eficiente e como implementá-lo em Python 🐍 — mesmo que você esteja dando seus primeiros passos na programação.

🧠 O que é Pesquisa Binária?

A pesquisa binária é um método para encontrar um item dentro de uma lista ordenada. Isso é importante: a lista precisa estar em ordem crescente (ou decrescente, com ajustes). O algoritmo funciona dividindo a lista ao meio repetidamente, até encontrar o que você está procurando — ou até ter certeza de que o item não está lá.

Imagine que você tem uma lista com 1000 números. Em vez de verificar um por um (como na busca linear), a pesquisa binária começa no meio. Se o número do meio for menor que o que você procura, ela ignora toda a metade esquerda. Isso reduz o número de comparações drasticamente. É como mágica, mas com lógica! ✨

🧪 Um Exemplo do Mundo Real

Vamos imaginar que você está procurando o número 9 em uma lista ordenada como esta:

[1, 3, 5, 7, 9, 11, 13, 15]
Enter fullscreen mode Exit fullscreen mode

Você começa olhando para o número do meio: é o 7. Como 9 é maior que 7, você ignora todos os números à esquerda de 7. Agora sua nova lista é:

[9, 11, 13, 15]
Enter fullscreen mode Exit fullscreen mode

O novo meio é 11. Mas 9 é menor que 11, então você ignora os números à direita. Agora só resta o 9. E voilà! 🎯

🛠️ Como Implementar em Python

Vamos construir o código juntos, passo a passo. Não se preocupe se você nunca fez isso antes — vou explicar cada linha com carinho 💡

1. Começando a função 

def pesquisa_binaria(lista, alvo):
    inicio = 0
    fim = len(lista) - 1
Enter fullscreen mode Exit fullscreen mode

Aqui estamos criando uma função chamada pesquisa_binaria. Ela recebe dois parâmetros: a lista (que deve estar ordenada) e o alvo (o número que queremos encontrar). As variáveis inicio e fim representam os limites da parte da lista que estamos analisando.

2. O coração da busca 

    while inicio <= fim:
        meio = (inicio + fim) // 2
        chute = lista[meio]
Enter fullscreen mode Exit fullscreen mode

Enquanto ainda houver elementos para verificar, calculamos o índice do meio da lista. O // é uma divisão inteira — ele garante que o resultado seja um número inteiro. O chute é o valor que está nesse índice.

3. Comparando o chute com o alvo 

        if chute == alvo:
            return meio
        elif chute < alvo:
            inicio = meio + 1
        else:
            fim = meio - 1
Enter fullscreen mode Exit fullscreen mode

Aqui é onde a mágica acontece ✨:

  • Se o chute for igual ao alvo, encontramos o número e retornamos sua posição.
  • Se o chute for menor, descartamos a metade esquerda da lista.
  • Se for maior, descartamos a metade direita.

4. E se não encontrarmos? 

    return -1
Enter fullscreen mode Exit fullscreen mode

Se o loop terminar e não encontrarmos o número, retornamos -1 para indicar que ele não está na lista.

✅ Código Completo 

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

    while inicio <= fim:
        meio = (inicio + fim) // 2
        chute = lista[meio]

        if chute == alvo:
            return meio
        elif chute < alvo:
            inicio = meio + 1
        else:
            fim = meio - 1

    return -1

# Testando a função
numeros = [1, 3, 5, 7, 9, 11, 13, 15]
procurado = 9

resultado = pesquisa_binaria(numeros, procurado)

if resultado != -1:
    print(f"Encontrado no índice {resultado}")
else:
    print("Número não encontrado")
Enter fullscreen mode Exit fullscreen mode

🚀 Por que usar Pesquisa Binária?

A pesquisa binária é incrivelmente eficiente. Enquanto a busca linear pode levar até n passos (no pior caso), a pesquisa binária leva no máximo log₂(n) passos. Isso significa que, para uma lista com 1.000.000 de itens, você só precisa de cerca de 20 comparações! 😲

⚠️ Cuidados Importantes

  • A lista precisa estar ordenada. Se não estiver, o algoritmo pode falhar.
  • Funciona com números, strings ou qualquer coisa que possa ser comparada com <, > e ==.

🧠 Conclusão

A pesquisa binária é um daqueles algoritmos que parecem simples, mas são incrivelmente poderosos. Saber usá-la é um passo importante na sua jornada como programador(a). E o melhor: agora você já sabe como ela funciona! 🎉

Top comments (0)