Busca¶
Uma busca retorna um valor correspondente, sua posição ou um limite no qual ele poderia ser inserido. A estrutura da entrada determina o que é possível.
| Algoritmo | Entrada necessária | Tempo no pior caso | Espaço auxiliar |
|---|---|---|---|
| Busca linear | Qualquer sequência finita | Θ(n) |
Θ(1) |
| Busca binária | Sequência ordenada com acesso aleatório | Θ(log n) |
Θ(1) na versão iterativa |
| Busca em hash | Tabela hash e hashing adequado | Θ(n), esperado O(1) |
Depende da estrutura |
| Busca em árvore balanceada | Árvore de busca ordenada e balanceada | Θ(log n) |
Depende da estrutura |
Ordenar apenas para fazer uma busca binária normalmente custa mais do que percorrer a entrada uma vez. A ordenação pode compensar quando muitas consultas posteriores reutilizam os mesmos dados ordenados.