Busca
Linear, binária e por hash — as três respostas para 'está aqui?', e o que cada uma exige.
Procurar é a operação mais comum que existe, e há três formas com custos muito diferentes. A escolha depende de uma pergunta: o que você sabe sobre os dados antes de procurar?
| Forma | Custo | Exige |
|---|---|---|
percorrer (x in lista) | O(n) | nada |
binária (busca_binaria) | O(log n) | a lista ordenada |
hash (x in set / vault) | O(1) | valores imutáveis; memória extra |
dataforge
adopt Arcane.Algoritmos as Alg
ordenada := [2, 3, 5, 7, 11, 13, 17, 19, 23]
assert Alg.busca_binaria(ordenada, 13) is 5
assert Alg.busca_binaria(ordenada, 4) is -1
assert Alg.limite_inferior(ordenada, 4) is 2 // onde o 4 entraria
// Um milhao de itens: a binaria olha no maximo ~20.
xs := range(0, 1000000)
assert Alg.busca_binaria(xs, 765432) is 765432
out $"log2(1.000.000) = {round(log2(1000000), 1)} passos, no pior caso"Quando ordenar vale a pena#
Ordenar custa O(n log n). Se você vai procurar uma vez, percorrer (O(n)) é mais barato. Se vai procurar k vezes, ordenar e usar binária custa O(n log n + k log n) contra O(k·n) — e para k grande, a diferença é de horas. E se não precisa de ordem, um set responde em O(1) sem ordenar nada.