Algoritmos de Busca
Algoritmos de Busca em Estruturas de Dados
Algoritmos de busca são técnicas para localizar elementos em estruturas de dados. São essenciais em concursos públicos, especialmente para questões de eficiência e aplicações práticas.
1. Busca Linear (Sequencial)
Percorre cada elemento de uma lista/array até encontrar o alvo. Não exige dados ordenados.
- Complexidade: O(n) no pior caso
- Uso: Listas pequenas ou não ordenadas
2. Busca Binária
Divide repetidamente uma lista ORDENADA ao meio, comparando o elemento central com o alvo.
- Complexidade: O(log n)
- Requisito: Dados pré-ordenados
- Variações: Iterativa e recursiva
3. Busca em Árvores (BST)
Explora a propriedade de árvores binárias de busca (left
- Complexidade: O(h), onde h = altura da árvore
- Melhor caso: O(1) se raiz for o alvo
- Pior caso: O(n) em árvores degeneradas
4. Busca em Grafos (BFS e DFS)
Dois principais métodos para percorrer grafos:
- BFS (Busca em Largura): Usa fila, explora vizinhos primeiro - ideal para caminhos mínimos
- DFS (Busca em Profundidade): Usa pilha (recursão), explora ramificações - memória eficiente
5. Tabela Hash (Hashing)
Acesso direto via função hash, ideal para implementar dicionários:
- Complexidade média: O(1) para inserção/busca
- Colisões: Tratadas por encadeamento ou endereçamento aberto
Dicas para Concursos
- Memorize complexidades no pior caso
- Diferencie requisitos (ex: binária exige ordenação)
- Relacione algoritmos a estruturas (ex: BST para árvores)
- Priorize questões sobre trade-offs (velocidade vs. memória)