Lançado · em melhoria
Algorithm
Algoritmos de busca encontram valores ou posições nos dados: busca linear, busca binária, lower_bound e upper_bound, busca binária na resposta e tabelas hash.
Buscar é encontrar um valor em uma coleção de dados, ou a posição em que uma condição passa a valer pela primeira vez. A busca linear verifica os elementos um a um e funciona com qualquer dado, enquanto a busca binária divide ao meio um intervalo ordenado a cada passo e precisa de apenas cerca de 20 comparações para um milhão de elementos. Para correspondências exatas, uma tabela hash responde em tempo constante, em média.
A busca é fundamental porque quase todo programa consulta dados: índices de banco de dados, autocompletar, análise de logs e tabelas de roteamento dependem dela. Além disso, a busca binária não se limita a arrays. Sempre que uma condição de sim ou não muda uma única vez ao longo de um intervalo, é possível fazer busca binária na própria resposta, o que transforma muitos problemas de otimização de entrevistas técnicas em código curto e confiável.
Comece escrevendo você mesmo uma busca linear e uma busca binária com intervalo fechado e depois pratique as formas lower_bound e upper_bound com intervalo semiaberto até que o tratamento dos limites fique natural. Acompanhe a execução em arrays pequenos à mão, compare seu código com o módulo bisect do Python usando entradas aleatórias e, por fim, pratique busca binária na resposta e busca ternária com problemas de otimização.
Compara os elementos um a um em tempo O(n). Não exige ordenação e, com poucos elementos, costuma ser a opção mais rápida.
Divide ao meio um intervalo ordenado a cada passo e encontra valores em tempo O(log n). A versão iterativa usa apenas O(1) de memória extra.
Retornam a primeira posição cujo valor é maior ou igual, ou estritamente maior, que o procurado. A diferença entre elas conta as duplicatas, e o módulo bisect do Python oferece as duas.
A busca paramétrica transforma a pergunta sobre o menor valor viável em um teste de sim ou não e faz busca binária no intervalo de respostas possíveis.
lower_bound retorna o primeiro índice cujo valor é maior ou igual a x, trabalhando no intervalo semiaberto [lo, hi). Se o valor do meio for menor que x, descarta a metade esquerda; caso contrário, a direita. contains usa esse índice para verificar se o valor existe, e a última linha confirma que o resultado é igual ao de bisect.bisect_left da biblioteca padrão.
searching.py
from bisect import bisect_left
def lower_bound(a, x):
"""Return the first index i with a[i] >= x (len(a) if there is none)."""
lo, hi = 0, len(a)
while lo < hi:
mid = (lo + hi) // 2
if a[mid] < x:
lo = mid + 1
else:
hi = mid
return lo
def contains(a, x):
i = lower_bound(a, x)
return i < len(a) and a[i] == x
if __name__ == "__main__":
data = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
print(lower_bound(data, 23), contains(data, 23)) # 5 True
print(lower_bound(data, 24), contains(data, 24)) # 6 False
print(lower_bound(data, 24) == bisect_left(data, 24)) # True
python searching.pySeis capítulos que levam você da instalação aos conceitos essenciais de Busca.
Tire dúvidas, compartilhe experiências e troque opiniões sobre Busca.
Ainda não há discussões. Comece a primeira.
0 comentários
Fazer login · Faça login para deixar um comentário.
Seja o primeiro a comentar.