24 de Março
Binary Search
O que binary search significa, quando dividir o espaço pela metade faz sentido e por que ordenação não é o único pré-requisito.
O que é
Binary search é procurar reduzindo metade do espaço a cada passo.
Em vez de andar item por item, você usa o meio para decidir se a resposta está de um lado ou do outro.
Quando usar
O caso mais óbvio é coleção ordenada.
Mas o padrão também aparece quando existe uma condição monotônica, do tipo:
- até aqui não serve
- daqui para frente serve
Erro comum
O erro clássico é decorar “só funciona em array ordenado” e parar aí.
Na prática, ele também serve para achar o primeiro ponto em que uma condição passa a ser verdadeira.
Pergunta melhor
Antes de aplicar, vale perguntar:
- consigo descartar metade da busca com segurança?
- existe uma ordem ou monotonicidade real?
- estou procurando um valor exato ou um limite?
Compartilhar esta página
Copie o link manualmente no campo abaixo.