📚 Algoritmos de Busca: Binary Search, DFS e BFS
Os algoritmos de busca são fundamentais na ciência da computação, pois permitem localizar informações ou percorrer estruturas de dados de forma eficiente. Eles aparecem em problemas que vão desde pesquisa em bancos de dados, até navegação em mapas, jogos, inteligência artificial e redes sociais.
Entre os mais importantes estão:
Busca Binária (Binary Search)
Busca em Profundidade (Depth-First Search – DFS)
Busca em Largura (Breadth-First Search – BFS)
🔹 1. Busca Binária (Binary Search)
A busca binária é um algoritmo eficiente para encontrar elementos em listas ordenadas. A ideia é dividir o espaço de busca repetidamente pela metade, reduzindo drasticamente o número de comparações.
Funcionamento:
Escolhe o elemento do meio do array.
Se for o elemento buscado → fim.
Se o elemento buscado for menor, busca na metade esquerda.
Se for maior, busca na metade direita.
Repete até encontrar ou esgotar os elementos.
Exemplo:
Array ordenado: [1, 3, 5, 7, 9, 11] Busca pelo número 7:
Meio = 5 → 7 > 5 → busca na metade direita.
Meio = 9 → 7 < 9 → busca na metade esquerda.
Encontra 7.
Complexidade:
O(log n) no pior caso (divide pela metade a cada passo).
Muito mais eficiente que a busca linear (O(n)), quando os dados estão ordenados.
🔹 2. Busca em Profundidade (DFS – Depth-First Search)
A DFS é usada para percorrer grafos e árvores. Ela segue o princípio de explorar o mais fundo possível em um caminho antes de retroceder.
Funcionamento:
Começa em um nó inicial.
Visita um vizinho não visitado e repete recursivamente.
Se não houver vizinhos, retorna ao nó anterior (backtracking).
Repete até visitar todos os nós alcançáveis.
Estrutura usada:
Pilha (stack) ou recursão.
Aplicações:
Detectar ciclos em grafos.
Resolver labirintos.
Ordenação topológica.
Inteligência artificial (busca em jogos).
Complexidade:
O(V + E), onde V = vértices e E = arestas do grafo.
🔹 3. Busca em Largura (BFS – Breadth-First Search)
A BFS também percorre grafos/árvores, mas segue o princípio de explorar primeiro os vizinhos mais próximos, antes de passar ao próximo nível.
Funcionamento:
Começa em um nó inicial.
Visita todos os vizinhos imediatos.
Depois, visita os vizinhos dos vizinhos, e assim por diante.
Estrutura usada:
Fila (queue).
Aplicações:
Encontrar o caminho mais curto em grafos não ponderados.
Redes sociais (pessoas a 1°, 2°, 3° grau de conexão).
Busca em mapas e labirintos.
Complexidade:
O(V + E), igual à DFS.
📊 Comparação Geral Algoritmo Estrutura usada Estrutura de dados alvo Objetivo principal Complexidade Busca Binária Divisão recursiva Array ordenado Encontrar elemento rapidamente O(log n) DFS Pilha / recursão Grafo ou árvore Explorar em profundidade O(V + E) BFS Fila Grafo ou árvore Explorar em largura / menor caminho O(V + E) 🎯 Conclusão
A Busca Binária é ideal quando lidamos com listas ordenadas e precisamos localizar elementos com rapidez.
A DFS e a BFS são cruciais em estruturas conectadas (grafos/árvores), sendo usadas para exploração sistemática e resolução de problemas de caminhos.
Cada algoritmo tem sua força em contextos específicos:
Busca binária → eficiência em arrays ordenados.
DFS → profundidade, exploração completa, backtracking.
BFS → largura, menor caminho em grafos não ponderados.
GRAFOS
- O que estamos tentando modelar?
Temos 4 cidades:
Luanda
Benguela
Lubango
Namibe
E estradas entre elas:
Luanda ↔ Benguela
Luanda ↔ Lubango
Benguela ↔ Namibe
Lubango ↔ Namibe
🔹 2. Como transformar em números?
Como o computador não entende "Luanda" ou "Benguela", damos um número para cada cidade:
Luanda = 1 Benguela = 2 Lubango = 3 Namibe = 4
🔹 3. Criando a matriz
Agora fazemos uma tabela 4x4 (porque temos 4 cidades).
Cada linha e cada coluna representam uma cidade.
Se existe estrada entre as duas cidades, colocamos 1.
Se não existe, colocamos 0.
Exemplo:
1 2 3 4
-----------------
1 | 0 1 1 0 2 | 1 0 0 1 3 | 1 0 0 1 4 | 0 1 1 0
👉 Como ler:
Linha 1, Coluna 2 = 1 → Luanda (1) está ligada a Benguela (2).
Linha 1, Coluna 3 = 1 → Luanda (1) está ligada a Lubango (3).
Linha 2, Coluna 4 = 1 → Benguela (2) está ligada a Namibe (4).
Linha 3, Coluna 4 = 1 → Lubango (3) está ligada a Namibe (4).
Todos os outros números são 0 → não há estrada.