Como funciona a busca binária e o que ela exige?

Question

IT Interview Practice · Accepted Answer

**Binary search** encontra um alvo em um array **ordenado** reduzindo repetidamente o intervalo de busca pela metade. Cada comparação elimina metade dos elementos restantes, resultando em tempo **O(log n)**. ## A ideia Olhe para o elemento do meio. Se for igual ao alvo, pronto. Se o alvo for menor, procure na metade esquerda; se for maior, procure na metade direita. Repita até encontrar ou o intervalo ficar vazio. ## Exemplo ```python def binary_search(arr, target): lo, hi = 0, len(arr) - 1 while lo <= hi: mid = (lo + hi) // 2 # middle index if arr[mid] == target: return mid # found it elif arr[mid] < target: lo = mid + 1 # discard left half else: hi = mid - 1 # discard right half return -1 # not present binary_search([1, 3, 5, 7, 9], 7) # -> 3 ``` ## Rastreamento ```text Search 7 in [1,3,5,7,9] lo=0 hi=4 mid=2 -> 5 < 7 => lo=3 lo=3 hi=4 mid=3 -> 7 == 7 => return 3 ``` ## Complexidade - **Tempo:** O(log n). **Espaço:** O(1) iterativo. ## Armadilhas A **entrada deve estar ordenada** — caso contrário, os resultados não fazem sentido. Cuidado com erros off-by-one em `lo`/`hi` e overflow de inteiros em algumas linguagens (use `lo + (hi-lo)//2`). ## Por que isso importa Reduzir o espaço de busca pela metade transforma uma busca em um milhão de elementos em ~20 comparações. O padrão dividir-e-conquistar por trás disso reaparece em árvores, bancos de dados e inúmeros problemas de entrevista. Conhecer seu único requisito rigoroso — entrada ordenada — o mantém longe de um clássico bug sutil.

A ideia

Exemplo

Rastreamento

Complexidade

Armadilhas

Por que isso importa

Perguntas relacionadas