# Busca (Search Algorithms)

### 📌 Visão Geral

Algoritmos de **busca** são fundamentais em ciência da computação e permitem localizar elementos específicos em estruturas de dados. A escolha do algoritmo correto pode significar a diferença entre uma resposta em milissegundos ou em horas.

```
Entrada: Lista de dados + Elemento alvo
    ↓
Algoritmo de Busca
    ↓
Saída: Posição do elemento (ou "não encontrado")
```

#### Analogia

> *"Buscar um nome em uma lista telefônica de 1 milhão de entradas: folhear página por página (busca linear) ou ir direto para a letra correta (busca binária)?"*

***

### 📋 Classificação dos Algoritmos

#### Busca em Listas (Estruturas Lineares)

| Algoritmo                  | Pré-requisito               | Complexidade | Melhor Caso | Tipo               |
| -------------------------- | --------------------------- | ------------ | ----------- | ------------------ |
| **Busca Linear**           | Nenhum                      | O(n)         | O(1)        | Sequencial         |
| **Busca Binária**          | Dados ordenados             | O(log n)     | O(1)        | Dividir/Conquistar |
| **Busca por Interpolação** | Dados ordenados + uniformes | O(log log n) | O(1)        | Estimativa         |
| **Busca por Salto**        | Dados ordenados             | O(√n)        | O(√n)       | Blocos             |

#### Busca em Grafos (Estruturas Não Lineares)

| Algoritmo      | Pré-requisito         | Complexidade | Tipo                    |
| -------------- | --------------------- | ------------ | ----------------------- |
| **BFS**        | Nenhum                | O(V + E)     | Largura (não ponderado) |
| **DFS**        | Nenhum                | O(V + E)     | Profundidade            |
| **Best-First** | Função heurística     | O(E)         | Guloso                  |
| **A**\*        | Heurística admissível | O(E)         | Ótimo                   |

***

### 🔢 Busca em Listas

#### 1. Busca Linear (Sequencial)

**Como funciona:** Percorre cada elemento da lista até encontrar o alvo.

```python
def busca_linear(lista, alvo):
    for i, elemento in enumerate(lista):
        if elemento == alvo:
            return i
    return -1

# Exemplo
lista = [5, 2, 8, 1, 9, 3]
posicao = busca_linear(lista, 8)  # Retorna 2
```

| Vantagem                          | Desvantagem                        |
| --------------------------------- | ---------------------------------- |
| ✅ Funciona em dados não ordenados | ❌ Lenta para listas grandes (O(n)) |
| ✅ Simples de implementar          |                                    |

**Quando usar:** Listas pequenas (n < 100) ou dados não ordenados.

***

#### 2. Busca Binária

**Como funciona:** Divide a lista ordenada em metades a cada iteração.

```python
def busca_binaria(lista, alvo):
    esquerda, direita = 0, len(lista) - 1
    
    while esquerda <= direita:
        meio = (esquerda + direita) // 2
        
        if lista[meio] == alvo:
            return meio
        elif lista[meio] < alvo:
            esquerda = meio + 1
        else:
            direita = meio - 1
    return -1

# Exemplo (lista precisa estar ordenada!)
lista = [1, 2, 3, 5, 8, 9]
posicao = busca_binaria(lista, 8)  # Retorna 4
```

| Vantagem                    | Desvantagem              |
| --------------------------- | ------------------------ |
| ✅ Muito rápida O(log n)     | ❌ Requer dados ordenados |
| ✅ Ótima para listas grandes |                          |

**Quando usar:** Listas grandes (n > 1000) e ordenadas.

**Visualização:** n=1.000.000 → apenas 20 iterações!

***

#### 3. Busca por Interpolação

**Como funciona:** Estima a posição do alvo baseado no valor (como procurar um nome em um dicionário).

```python
def busca_interpolacao(lista, alvo):
    esquerda, direita = 0, len(lista) - 1
    
    while esquerda <= direita and lista[esquerda] <= alvo <= lista[direita]:
        # Fórmula de interpolação
        posicao = esquerda + ((alvo - lista[esquerda]) * (direita - esquerda)) // (lista[direita] - lista[esquerda])
        
        if lista[posicao] == alvo:
            return posicao
        elif lista[posicao] < alvo:
            esquerda = posicao + 1
        else:
            direita = posicao - 1
    return -1

# Exemplo (dados uniformemente distribuídos)
lista = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]
posicao = busca_interpolacao(lista, 70)  # Retorna 6
```

| Vantagem                           | Desvantagem                               |
| ---------------------------------- | ----------------------------------------- |
| ✅ Extremamente rápida O(log log n) | ❌ Requer dados uniformemente distribuídos |
| ✅ Menos iterações que binária      | ❌ Pior caso O(n)                          |

**Quando usar:** Dados ordenados com distribuição uniforme (ex: IDs sequenciais, temperaturas).

***

#### 4. Busca por Salto (Jump Search)

**Como funciona:** Avança em blocos de tamanho √n e depois faz busca linear no bloco.

```python
import math

def busca_salto(lista, alvo):
    n = len(lista)
    passo = int(math.sqrt(n))
    
    # Encontrar o bloco correto
    anterior = 0
    while anterior < n and lista[min(passo, n)-1] < alvo:
        anterior = passo
        passo += int(math.sqrt(n))
        if anterior >= n:
            return -1
    
    # Busca linear no bloco
    for i in range(anterior, min(passo, n)):
        if lista[i] == alvo:
            return i
    return -1

# Exemplo
lista = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
posicao = busca_salto(lista, 15)  # Retorna 7
```

| Vantagem                   | Desvantagem        |
| -------------------------- | ------------------ |
| ✅ Melhor que linear        | ❌ Pior que binária |
| ✅ Útil para listas grandes |                    |

**Quando usar:** Listas ordenadas onde acesso a índices é caro (ex: fitas magnéticas).

***

#### Comparação de Complexidades (n = 1.000.000)

| Algoritmo        | Iterações (pior caso) | Tempo Estimado    |
| ---------------- | --------------------- | ----------------- |
| **Linear**       | 1.000.000             | 1 segundo         |
| **Salto**        | \~1.000               | 1 milissegundo    |
| **Binária**      | \~20                  | 20 microssegundos |
| **Interpolação** | \~3-5                 | 5 microssegundos  |

***

### 🌲 Busca em Grafos

#### 5. BFS - Busca em Largura (Breadth-First Search)

**Como funciona:** Explora o grafo nível por nível (como uma onda).

```python
from collections import deque

def bfs(grafo, inicio, alvo):
    visitados = set()
    fila = deque([inicio])
    distancia = {inicio: 0}
    
    while fila:
        vertice = fila.popleft()
        
        if vertice == alvo:
            return distancia[vertice]
        
        for vizinho in grafo[vertice]:
            if vizinho not in visitados:
                visitados.add(vizinho)
                fila.append(vizinho)
                distancia[vizinho] = distancia[vertice] + 1
    return -1

# Exemplo
grafo = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}
distancia = bfs(grafo, 'A', 'F')  # Retorna 2 (A→C→F)
```

| Vantagem                                        | Desvantagem            |
| ----------------------------------------------- | ---------------------- |
| ✅ Encontra o caminho mais curto (não ponderado) | ❌ Consome mais memória |
| ✅ Completo (sempre encontra solução)            |                        |

**Quando usar:** Grafos não ponderados, encontrar menor número de passos.

***

#### 6. DFS - Busca em Profundidade (Depth-First Search)

**Como funciona:** Explora o grafo até o fundo antes de voltar.

```python
def dfs(grafo, inicio, alvo, visitados=None):
    if visitados is None:
        visitados = set()
    
    if inicio == alvo:
        return True
    
    visitados.add(inicio)
    
    for vizinho in grafo[inicio]:
        if vizinho not in visitados:
            if dfs(grafo, vizinho, alvo, visitados):
                return True
    return False

# Exemplo (mesmo grafo)
existe = dfs(grafo, 'A', 'F')  # Retorna True
```

| Vantagem                         | Desvantagem                              |
| -------------------------------- | ---------------------------------------- |
| ✅ Menor uso de memória           | ❌ Não garante caminho mais curto         |
| ✅ Útil para problemas de decisão | ❌ Pode entrar em loops (requer controle) |

**Quando usar:** Labirintos, problemas de decisão, ordenação topológica.

***

#### 7. Best-First Search (Guloso)

**Como funciona:** Usa heurística para explorar primeiro os nós mais promissores.

```python
import heapq

def best_first_search(grafo, inicio, alvo, heuristica):
    visitados = set()
    heap = [(heuristica(inicio), inicio, [inicio])]
    
    while heap:
        _, vertice, caminho = heapq.heappop(heap)
        
        if vertice == alvo:
            return caminho
        
        if vertice in visitados:
            continue
        
        visitados.add(vertice)
        
        for vizinho in grafo[vertice]:
            if vizinho not in visitados:
                heapq.heappush(heap, (heuristica(vizinho), vizinho, caminho + [vizinho]))
    return None

# Exemplo: encontrar caminho para saída de labirinto
def heuristica_manhattan(posicao):
    # Distância de Manhattan até o alvo (exemplo)
    alvo = (5, 5)
    return abs(posicao[0] - alvo[0]) + abs(posicao[1] - alvo[1])
```

| Vantagem                     | Desvantagem                             |
| ---------------------------- | --------------------------------------- |
| ✅ Muito rápido               | ❌ Não garante caminho ótimo             |
| ✅ Boa para problemas grandes | ❌ Pode ser enganado por heurística ruim |

***

#### 8. A\* (A-Estrela)

**Como funciona:** Combina custo real (g) + heurística (h) = f(n). Garante caminho ótimo.

```python
import heapq

def a_star(grafo, inicio, alvo, heuristica):
    # g-score: custo do início até o nó
    g_score = {inicio: 0}
    # f-score: g_score + heurística
    f_score = {inicio: heuristica(inicio, alvo)}
    
    heap = [(f_score[inicio], inicio)]
    caminho = {inicio: None}
    
    while heap:
        _, atual = heapq.heappop(heap)
        
        if atual == alvo:
            # Reconstruir caminho
            caminho_completo = []
            while atual:
                caminho_completo.append(atual)
                atual = caminho[atual]
            return caminho_completo[::-1]
        
        for vizinho, custo in grafo[atual].items():
            g_tentativo = g_score[atual] + custo
            
            if vizinho not in g_score or g_tentativo < g_score[vizinho]:
                g_score[vizinho] = g_tentativo
                f_score[vizinho] = g_tentativo + heuristica(vizinho, alvo)
                caminho[vizinho] = atual
                heapq.heappush(heap, (f_score[vizinho], vizinho))
    
    return None

# Exemplo: GPS com distância real (g) + distância em linha reta (h)
```

| Vantagem                    | Desvantagem             |
| --------------------------- | ----------------------- |
| ✅ Garante caminho ótimo     | ❌ Requer boa heurística |
| ✅ Muito eficiente           | ❌ Pode consumir memória |
| ✅ Padrão em sistemas de GPS |                         |

**Quando usar:** Sistemas de GPS, jogos (pathfinding), robótica.

***

### 📊 Comparação Visual

#### Tempo de Busca (n = 1.000.000)

```
Linear:     ████████████████████████████████████████ (1.000.000 ops)
Salto:      ████ (1.000 ops)
Binária:    █ (20 ops)
Interpolação: ▏ (3-5 ops)
```

#### Busca em Grafos - Características

| Algoritmo      | Completo | Ótimo                 | Tempo  | Espaço | Heurística |
| -------------- | -------- | --------------------- | ------ | ------ | ---------- |
| **BFS**        | ✅ Sim    | ✅ Sim (não ponderado) | O(V+E) | O(V)   | ❌ Não      |
| **DFS**        | ✅ Sim    | ❌ Não                 | O(V+E) | O(d)   | ❌ Não      |
| **Best-First** | ✅ Sim    | ❌ Não                 | O(E)   | O(V)   | ✅ Sim      |
| **A**\*        | ✅ Sim    | ✅ Sim                 | O(E)   | O(V)   | ✅ Sim      |

***

### 🎯 Guia Rápido de Seleção

#### "Preciso encontrar um elemento em uma lista..."

| Se seus dados são...          | Use                    |
| ----------------------------- | ---------------------- |
| Pequenos (n < 100)            | Busca Linear           |
| Ordenados                     | Busca Binária          |
| Ordenados e uniformes         | Busca por Interpolação |
| Ordenados (acesso sequencial) | Busca por Salto        |

#### "Preciso encontrar um caminho em um grafo..."

| Se seu problema é...                         | Use                             |
| -------------------------------------------- | ------------------------------- |
| Caminho mais curto (não ponderado)           | BFS                             |
| Existe um caminho? (decisão)                 | DFS                             |
| Labirinto com heurística (não precisa ótimo) | Best-First                      |
| GPS / Caminho mais curto (ponderado)         | A\*                             |
| Menor distância (pesos positivos)            | Dijkstra (ver diretório Grafos) |

***

### 💻 Exemplos Rápidos

#### Busca Binária (Python - Biblioteca)

```python
import bisect

lista = [1, 3, 5, 7, 9, 11, 13]
posicao = bisect.bisect_left(lista, 7)  # Retorna 3
```

#### BFS para Menor Caminho (NetworkX)

```python
import networkx as nx

G = nx.Graph()
G.add_edges_from([('A','B'), ('A','C'), ('B','D'), ('C','D')])
caminho = nx.shortest_path(G, 'A', 'D')  # Retorna ['A', 'C', 'D']
```

***

### 🔗 Links Úteis

* [Visualização de Busca Binária](https://visualgo.net/en/bst)
* [Visualização de BFS/DFS](https://visualgo.net/en/dfsbfs)
* [Pathfinding (A\*, Dijkstra)](https://visualgo.net/en/sssp)

***

### 📚 Complexidades Resumidas

| Algoritmo        | Melhor | Médio        | Pior     |
| ---------------- | ------ | ------------ | -------- |
| **Linear**       | O(1)   | O(n/2)       | O(n)     |
| **Binária**      | O(1)   | O(log n)     | O(log n) |
| **Interpolação** | O(1)   | O(log log n) | O(n)     |
| **Salto**        | O(√n)  | O(√n)        | O(√n)    |
| **BFS**          | O(V+E) | O(V+E)       | O(V+E)   |
| **DFS**          | O(V+E) | O(V+E)       | O(V+E)   |
| **A**\*          | O(1)   | O(E)         | O(E)     |


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://0xmorte.gitbook.io/bibliadopentestbr/conceitos/algoritmos/busca-search-algorithms.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.