0Pricing
DSA Interview Prep · Aula

Busca Binária Clássica: Esquerda, Direita, Meio

Implemente a busca binária iterativa e recursivamente, domine os detalhes de limites lo/hi e verifique a correção com entradas de casos extremos.

Busca Binária Clássica: Esquerda, Direita, Meio é uma aula grátis de DSA Interview Prep no CoddyKit. Esta é a aula 1 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de DSA Interview Prep, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de DSA Interview Prep inclui 4 aulas no total.

Por que a busca binária é importante

A busca binária reduz uma varredura linear O(n) a O(log n) ao dividir pela metade o espaço de busca em cada etapa. Em um vetor com um milhão de elementos, uma varredura linear pode exigir até 1.000.000 de comparações, mas a busca binária precisa de no máximo 20. Essa eficiência faz dela um dos algoritmos mais cobrados em entrevistas de programação.

A ideia central é que um vetor ordenado permite decidir, após uma única comparação, qual metade dos dados restantes pode ser descartada por completo.

A estrutura esquerda, meio, direita

A busca binária usa três ponteiros de índice: lo (limite esquerdo), hi (limite direito) e mid (ponto central). Em cada iteração, calcule mid = (lo + hi) // 2 e compare o alvo com arr[mid]. Se o alvo for menor, mova hi = mid - 1; se for maior, mova lo = mid + 1; se for igual, você o encontrou.

O laço continua enquanto lo <= hi. Quando ele termina sem encontrar o alvo, retorne -1.

def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

print(binary_search([1, 3, 5, 7, 9, 11], 7))  # 3
print(binary_search([1, 3, 5, 7, 9, 11], 6))  # -1

Evitando estouro de inteiros em mid

A expressão mid = (lo + hi) // 2 pode causar estouro de inteiros em linguagens que usam inteiros de largura fixa (Java, C++). Os inteiros do Python têm precisão arbitrária, portanto nunca ocorre estouro, mas os entrevistadores ainda esperam que você conheça a alternativa segura: mid = lo + (hi - lo) // 2.

Essa forma calcula o mesmo ponto central, mas adiciona apenas metade da distância a lo, em vez de somar primeiro os dois ponteiros. Mencionar isso em uma entrevista demonstra que você está atento a questões de baixo nível.

# Safe mid calculation (important in Java/C++, good habit in Python too)
lo, hi = 0, 1_000_000_000
mid_unsafe = (lo + hi) // 2   # fine in Python
mid_safe   = lo + (hi - lo) // 2  # same result, no overflow risk
print(mid_unsafe == mid_safe)  # True

Limites inclusivos e exclusivos

Uma das partes mais difíceis da busca binária é escolher se hi aponta para o último índice válido (inclusivo, hi = len(arr) - 1) ou para uma posição após o fim (exclusivo, hi = len(arr)). Convenções diferentes exigem condições de laço e atualizações de limites diferentes.

Com limites inclusivos, use while lo <= hi e atualize hi = mid - 1. Com limites exclusivos, use while lo < hi e atualize hi = mid. Misturar as convenções é a fonte mais comum de erros nas implementações de busca binária.

# Exclusive hi variant — useful for bisect-style lower-bound
def search_exclusive(arr, target):
    lo, hi = 0, len(arr)  # hi is one past last
    while lo < hi:          # strictly less than
        mid = lo + (hi - lo) // 2
        if arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid         # NOT mid - 1
    return lo if lo < len(arr) and arr[lo] == target else -1

print(search_exclusive([2, 4, 6, 8, 10], 6))  # 2

Busca binária recursiva

A busca binária pode ser escrita de forma recursiva, passando os limites atualizados lo e hi pela pilha de chamadas. Cada chamada recursiva reduz o espaço de busca pela metade, portanto a profundidade é O(log n). O caso-base ocorre quando lo > hi (não encontrado) ou quando arr[mid] == target (encontrado).

A versão iterativa é preferível no código de produção porque evita a sobrecarga dos quadros da pilha, mas a versão recursiva comunica com mais clareza a estrutura de dividir e conquistar em um quadro branco.

def binary_search_rec(arr, target, lo, hi):
    if lo > hi:
        return -1
    mid = lo + (hi - lo) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search_rec(arr, target, mid + 1, hi)
    else:
        return binary_search_rec(arr, target, lo, mid - 1)

arr = [1, 3, 5, 7, 9, 11]
print(binary_search_rec(arr, 9, 0, len(arr) - 1))  # 4

Casos-limite: vetor vazio, elemento único

Uma busca binária robusta deve lidar com casos-limite sem falhar. Os três mais comuns são: um vetor vazio (o laço nunca é executado e -1 é retornado corretamente), um vetor com um único elemento (mid é igual a lo e a hi, portanto uma comparação basta) e alvos fora do intervalo (lo acaba ultrapassando hi e -1 é retornado).

Sempre verifique sua implementação com essas entradas antes de passar às perguntas seguintes em uma entrevista.

def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

print(binary_search([], 5))       # -1  (empty)
print(binary_search([7], 7))      # 0   (single, found)
print(binary_search([7], 3))      # -1  (single, not found)
print(binary_search([1,3,5], 0))  # -1  (below range)
print(binary_search([1,3,5], 9))  # -1  (above range)

Complexidade de tempo e espaço

A busca binária tem complexidade de tempo O(log n) porque cada comparação reduz pela metade o espaço de busca. Após k comparações, o espaço restante é n/2^k; a busca termina quando esse valor chega a 1, portanto k = log₂ n.

A complexidade de espaço é O(1) na versão iterativa (apenas três variáveis inteiras) e O(log n) na versão recursiva, devido à profundidade da pilha de chamadas. Em uma entrevista, sempre informe as duas complexidades e prefira a forma iterativa quando o espaço for limitado.

import math

for n in [10, 100, 1000, 1_000_000, 1_000_000_000]:
    steps = math.ceil(math.log2(n + 1))
    print(f'n={n:>12,}  max comparisons={steps}')

Busca por correspondência exata versus limite

A busca binária clássica retorna qualquer índice em que o alvo exista. Porém, muitos problemas de entrevista pedem a primeira ou a última ocorrência de um alvo. Nesses casos, você precisa continuar buscando mesmo depois de encontrar uma correspondência — em vez de retornar imediatamente, restrinja o limite e continue.

Ao procurar a primeira ocorrência, depois de encontrar arr[mid] == target, registre mid como candidato e defina hi = mid - 1. Para a última ocorrência, defina lo = mid + 1.

def first_occurrence(arr, target):
    lo, hi, result = 0, len(arr) - 1, -1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] == target:
            result = mid
            hi = mid - 1   # keep searching left
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return result

print(first_occurrence([1, 2, 2, 2, 3], 2))  # 1

Usando o módulo bisect do Python

A biblioteca padrão do Python fornece bisect.bisect_left(arr, x) e bisect.bisect_right(arr, x) para realizar buscas binárias prontas para produção. bisect_left retorna o índice mais à esquerda em que x pode ser inserido para manter o vetor ordenado, encontrando efetivamente a primeira posição em que arr[i] >= x.

Os entrevistadores podem permitir o uso de bisect; confirme sempre antes. Ainda é essencial saber como ele funciona internamente (é uma busca binária O(log n)).

import bisect

arr = [1, 2, 2, 2, 3, 5]

print(bisect.bisect_left(arr, 2))   # 1  (first 2)
print(bisect.bisect_right(arr, 2))  # 4  (after last 2)

# Check if target exists
target = 3
idx = bisect.bisect_left(arr, target)
print(idx < len(arr) and arr[idx] == target)  # True

Armadilhas comuns da busca binária

Três erros causam a maioria dos problemas de busca binária em entrevistas. Primeiro, condição de laço incorreta: usar < em vez de <= com limites inclusivos faz com que o último elemento restante seja ignorado. Segundo, atualização incorreta dos limites: esquecer o +1 ou o -1 cria um laço infinito quando lo == hi. Terceiro, operar sobre um vetor não ordenado: a busca binária só está correta para dados ordenados.

Antes de escrever qualquer busca binária, diga em voz alta: 'O vetor está ordenado, meus limites são inclusivos e meu laço executa enquanto lo <= hi.'

# BUG: infinite loop when lo == hi because hi = mid never moves past lo
def buggy(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo < hi:              # should be lo <= hi for exact-match
        mid = lo + (hi - lo) // 2
        if arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid            # stops, but never returns mid when found
    return lo if arr[lo] == target else -1

print(buggy([1, 3, 5, 7], 7))  # 3 (works here by luck)
print(buggy([1, 3, 5, 7], 1))  # 0 (correct)
print(buggy([1, 3, 5, 7], 4))  # -1 (correct)

Dicas de entrevista para busca binária

Quando encontrar um problema sobre um vetor ordenado, uma função monotonicamente crescente ou um espaço de busca que possa ser dividido ao meio, considere imediatamente a busca binária. Em uma entrevista, explique seu raciocínio: 'Como o vetor está ordenado, posso descartar metade dos elementos a cada comparação, obtendo O(log n).'

Sempre verifique sua solução com pelo menos três entradas: um valor no início, um valor no fim e um valor ausente. Informar proativamente a complexidade — 'tempo O(log n), espaço O(1)' — antes que perguntem demonstra fundamentos sólidos.

Verificação rápida

Teste sua compreensão dos conceitos de Estruturas de Dados & Algoritmos — Preparação para Entrevistas de Programação desta lição.

Resumo da lição

Nesta lição, você aprendeu: a busca binária reduz pela metade o espaço de busca a cada etapa, alcançando tempo O(log n); a convenção de limites inclusivos usa lo <= hi, com as atualizações lo = mid+1 e hi = mid-1; e para encontrar a primeira ou a última ocorrência, você continua buscando depois de uma correspondência, em vez de retornar imediatamente. A seguir, vamos explorar como a busca binária se estende a vetores rotacionados e não ordenados.

Perguntas Frequentes

A aula “Busca Binária Clássica: Esquerda, Direita, Meio” é grátis?

Sim — o texto completo de “Busca Binária Clássica: Esquerda, Direita, Meio” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de DSA Interview Prep, atualize para CoddyKit PRO. O curso de DSA Interview Prep inclui 4 aulas no total.

O que vou aprender em “Busca Binária Clássica: Esquerda, Direita, Meio”?

Implemente a busca binária iterativa e recursivamente, domine os detalhes de limites lo/hi e verifique a correção com entradas de casos extremos. Você pratica DSA Interview Prep com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.

Preciso ter experiência prévia para começar DSA Interview Prep?

Nenhuma experiência prévia é necessária. DSA Interview Prep no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 1 de 4.

Quanto tempo leva a aula “Busca Binária Clássica: Esquerda, Direita, Meio”?

A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.

Posso escrever e executar código nesta aula de DSA Interview Prep?

Sim. Cada aula de DSA Interview Prep inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.

Todas as aulas deste curso

  1. Busca Binária Clássica: Esquerda, Direita, Meio
  2. Busca Binária em Arrays Rotacionados e Não Ordenados
  3. Limite Inferior e Limite Superior
  4. Busca Binária no Espaço de Respostas
← Voltar para DSA Interview Prep