Algoritmos de Busca

Buscar um elemento dentro de uma estrutura de dados é uma operação comum em diversos sistemas, como controle de sensores, cadastros de dispositivos e mapeamento de comandos. A escolha do algoritmo de busca afeta diretamente o desempenho da aplicação.

Busca Linear (Sequencial)

Percorre o vetor elemento por elemento até encontrar o alvo ou chegar ao final.

Características

• Não exige que os dados estejam ordenados.
• Simples de implementar.
• Útil para vetores pequenos ou raramente pesquisados.

Complexidade

• Melhor caso: \( \mathcal{O}(1) \) (encontrado na primeira posição)
• Pior caso: \( \mathcal{O}(n) \)
• Média: \( \mathcal{O}(\frac{n}{2}) \)

Exemplo em C

int busca_linear(int arr[], int n, int alvo) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == alvo)
            return i;
    }
    return -1; // Não encontrado
}

Busca Binária

Requer que os dados estejam ordenados. A cada passo, compara o valor do meio com o valor buscado e descarta metade do vetor.

Características

• Muito mais eficiente em listas grandes e ordenadas.
• Usada em tabelas de calibração, catálogos de sensores, etc.

Complexidade

• Melhor caso: \( \mathcal{O}(1) \)
• Pior e médio caso: \( \mathcal{O}(\log n) \)

Exemplo em C

int busca_binaria(int arr[], int n, int alvo) {
    int inicio = 0, fim = n - 1;
    while (inicio <= fim) {
        int meio = (inicio + fim) / 2;
        if (arr[meio] == alvo)
            return meio;
        else if (arr[meio] < alvo)
            inicio = meio + 1;
        else
            fim = meio - 1;
    }
    return -1; // Não encontrado
}

Comparação

Prova da Complexidade \( \mathcal{O}(\log n) \) da Busca Binária

A busca binária é um algoritmo eficiente para encontrar um elemento em um vetor ordenado. A cada iteração, o espaço de busca é reduzido pela metade. A seguir, mostramos por que sua complexidade no pior caso é \( \mathcal{O}(\log n) \).

Raciocínio

A cada passo da busca binária, o vetor é dividido ao meio:

• Tamanho original do vetor: \( n \)
• Após 1 passo: \( \frac{n}{2} \)
• Após 2 passos: \( \frac{n}{4} \)
• Após 3 passos: \( \frac{n}{8} \)
• ...
• Após \( k \) passos: \( \frac{n}{2^k} \)

A busca termina quando resta apenas um único elemento, ou seja:

\[ \frac{n}{2^k} = 1 \]

Multiplicando ambos os lados por \( 2^k \):

\[ n = 2^k \]

Aplicando logaritmo base 2:

\[ \log_2(n) = k \]

Conclusão

O número de comparações no pior caso é:

\[ k = \log_2(n) \]

Portanto, a complexidade é:

\[ T(n) \in \mathcal{O}(\log n) \]

Observações

• A base do logaritmo não altera a classe de complexidade na notação assintótica:

\[ \mathcal{O}(\log_2 n) = \mathcal{O}(\log_{10} n) = \mathcal{O}(\log n) \]

• Se \( n \) não for uma potência de 2, o número de comparações é aproximadamente:

\[ \lfloor \log_2(n) \rfloor + 1 \]

Aplicações

A complexidade logarítmica da busca binária a torna extremamente eficiente para grandes conjuntos de dados ordenados, como:

• Tabelas de calibração de sensores
• Localização de parâmetros em LUTs (Look-Up Tables)
• Sistemas embarcados com requisitos de resposta rápida

Aplicações na Engenharia

• Verificação de status de sensores em tabelas.
• Mapeamento de códigos de erro.
• Localização rápida de parâmetros em tabelas LUT (Look-Up Table).