Algoritmos de busca

Nesta aula, vamos explorar os algoritmos de busca em C, fundamentais para localizar elementos em estruturas de dados. Você aprenderá desde a busca linear, simples e universal, até a eficiente busca binária, além da função bsearch da biblioteca padrão, que já vem pronta para uso. Ao final, você terá uma compreensão sólida de quando e como usar cada técnica, com exemplos práticos e exercícios para fixar o conhecimento.

A busca é uma operação recorrente em programação: seja em listas, arrays, bancos de dados ou arquivos, precisamos encontrar dados específicos. Dominar os algoritmos de busca é essencial para escrever código eficiente e correto. Vamos começar com os fundamentos e avançar para soluções mais sofisticadas.

Pré-requisitos

Antes de mergulharmos nos algoritmos, é importante que você esteja familiarizado com alguns conceitos básicos da linguagem C. Isso inclui o uso de arrays, ponteiros, funções e a manipulação de memória. Além disso, é recomendável ter compreensão de complexidade de algoritmos (notação Big-O), pois isso nos ajuda a avaliar a eficiência de cada método de busca.

Vamos revisar rapidamente os conceitos essenciais:

• Arrays: estruturas de dados que armazenam elementos do mesmo tipo em posições contíguas de memória.
• Ponteiros: variáveis que armazenam endereços de memória; essenciais para manipular arrays e funções como bsearch.
• Funções: blocos de código reutilizáveis; no caso da bsearch, precisamos passar uma função de comparação.
• Complexidade: medida de como o tempo de execução cresce com o tamanho da entrada. Usamos O(1), O(n), O(log n), etc.

Se você já domina esses tópicos, está pronto para aprender os algoritmos de busca. Caso contrário, revise-os antes de continuar, pois eles serão usados intensamente.

Busca linear

A busca linear é o algoritmo mais simples de busca: percorremos o array do início ao fim, comparando cada elemento com o valor procurado. Quando encontramos uma correspondência, retornamos a posição (ou o elemento). Se chegarmos ao final sem encontrar, retornamos um indicador de falha (como -1).

Sua complexidade é O(n) no pior caso, o que significa que, para um array de n elementos, podemos precisar de n comparações. Isso é aceitável para arrays pequenos ou não ordenados, mas ineficiente para grandes volumes de dados. A busca linear não exige que o array esteja ordenado, o que a torna versátil.

Vejamos uma implementação típica:

#include <stdio.h>

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

int main() {
    int arr[] = {4, 2, 7, 1, 9, 3};
    int n = sizeof(arr) / sizeof(arr[0]);
    int alvo = 7;
    int indice = busca_linear(arr, n, alvo);
    if (indice != -1) {
        printf("Elemento encontrado no índice %d\n", indice);
    } else {
        printf("Elemento não encontrado\n");
    }
    return 0;
}

Neste exemplo, a função busca_linear recebe o array, o tamanho e o valor alvo. Ela percorre com um laço for e retorna o índice assim que encontra. No main, testamos com um array não ordenado; funciona perfeitamente.

Uma variação comum é a busca linear com sentinela, que evita a verificação de limite a cada iteração, mas é um detalhe de otimização que não altera a complexidade. Em geral, use busca linear quando:

• O array é pequeno.
• O array não está ordenado.
• Você precisa encontrar a primeira ocorrência.

Busca binária

A busca binária é um algoritmo muito mais eficiente, com complexidade O(log n). No entanto, ela exige que o array esteja ordenado em ordem crescente (ou decrescente, se adaptarmos). A ideia é dividir o intervalo de busca pela metade a cada passo: comparamos o elemento do meio com o alvo e, se for maior, buscamos na metade esquerda; se for menor, na metade direita; se for igual, encontramos.

Esse processo reduz drasticamente o número de comparações. Por exemplo, para um array de 1.000.000 de elementos, a busca linear pode precisar de 1.000.000 de comparações, enquanto a binária faz no máximo 20 (pois 2^20 ≈ 1.048.576).

Implementação iterativa comum:

#include <stdio.h>

int busca_binaria(int arr[], int n, int alvo) {
    int esq = 0;
    int dir = n - 1;
    while (esq <= dir) {
        int meio = esq + (dir - esq) / 2; // evita overflow
        if (arr[meio] == alvo) {
            return meio;
        }
        if (arr[meio] < alvo) {
            esq = meio + 1;
        } else {
            dir = meio - 1;
        }
    }
    return -1;
}

int main() {
    int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    int n = sizeof(arr) / sizeof(arr[0]);
    int alvo = 7;
    int indice = busca_binaria(arr, n, alvo);
    if (indice != -1) {
        printf("Elemento encontrado no índice %d\n", indice);
    } else {
        printf("Elemento não encontrado\n");
    }
    return 0;
}

Observe o cálculo do meio: esq + (dir - esq) / 2 é uma forma segura de evitar overflow de inteiro, que pode ocorrer se usarmos (esq + dir) / 2 com números grandes. A condição esq <= dir garante que continuamos enquanto houver elementos no intervalo.

Também é possível implementar a busca binária de forma recursiva, mas a iterativa é geralmente mais eficiente em termos de uso de pilha. A versão recursiva é elegante e ajuda a entender o conceito:

int busca_binaria_rec(int arr[], int esq, int dir, int alvo) {
    if (esq > dir) return -1;
    int meio = esq + (dir - esq) / 2;
    if (arr[meio] == alvo) return meio;
    if (arr[meio] < alvo) return busca_binaria_rec(arr, meio+1, dir, alvo);
    else return busca_binaria_rec(arr, esq, meio-1, alvo);
}

Pré-requisito fundamental: o array deve estar ordenado. Se você tiver um array não ordenado, será necessário ordená-lo antes de usar busca binária, o que pode custar O(n log n) com algoritmos como quicksort ou mergesort. Para buscas únicas em dados não ordenados, a busca linear pode ser mais vantajosa.

bsearch da stdlib

A biblioteca padrão do C fornece a função bsearch, que implementa a busca binária de forma genérica. Ela pode ser usada com qualquer tipo de dado, desde que você forneça uma função de comparação. O protótipo é:

void *bsearch(const void *key, const void *base, size_t nmemb, size_t size,
              int (*compar)(const void *, const void *));

Parâmetros:

• key: ponteiro para o valor que se deseja encontrar.
• base: ponteiro para o primeiro elemento do array.
• nmemb: número de elementos no array.
• size: tamanho em bytes de cada elemento.
• compar: função de comparação que retorna negativo, zero ou positivo, similar ao strcmp.

A função retorna um ponteiro para o elemento encontrado, ou NULL se não existir. É importante que o array esteja ordenado de acordo com a mesma função de comparação.

Vamos ver um exemplo com inteiros:

#include <stdio.h>
#include <stdlib.h>

int compar_int(const void *a, const void *b) {
    int x = *(const int *)a;
    int y = *(const int *)b;
    return (x > y) - (x < y); // retorna -1, 0 ou 1
}

int main() {
    int arr[] = {1, 3, 5, 7, 9};
    int n = sizeof(arr) / sizeof(arr[0]);
    int alvo = 5;
    int *resultado = bsearch(&alvo, arr, n, sizeof(int), compar_int);
    if (resultado != NULL) {
        printf("Encontrado: %d\n", *resultado);
    } else {
        printf("Não encontrado\n");
    }
    return 0;
}

Perceba que passamos &alvo como chave, pois bsearch espera um ponteiro para o valor. A função de comparação compar_int converte os ponteiros void* para int* e compara. O retorno é a diferença normalizada para -1, 0, 1, mas pode ser qualquer inteiro negativo/positivo.

Podemos usar bsearch com outros tipos, como strings:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int compar_str(const void *a, const void *b) {
    // a e b são ponteiros para ponteiros de char
    return strcmp(*(const char **)a, *(const char **)b);
}

int main() {
    const char *nomes[] = {"ana", "bruno", "carla", "diego"};
    int n = sizeof(nomes) / sizeof(nomes[0]);
    const char *alvo = "carla";
    char **resultado = bsearch(&alvo, nomes, n, sizeof(char *), compar_str);
    if (resultado != NULL) {
        printf("Encontrado: %s\n", *resultado);
    } else {
        printf("Não encontrado\n");
    }
    return 0;
}

Aqui, o array é de ponteiros para char, então a função de comparação precisa desreferenciar duplamente. O key é um ponteiro para o ponteiro alvo.

Uma observação importante: bsearch não verifica se o array está ordenado; se não estiver, o comportamento é indefinido. Portanto, garanta a ordenação antes de chamá-la. Você pode usar qsort para ordenar, que é o complemento natural.

Boas práticas e observações finais

Ao escolher um algoritmo de busca, considere os seguintes pontos:

• Ordenação: se os dados são estáticos e você fará muitas buscas, vale a pena ordenar uma vez (O(n log n)) e usar busca binária O(log n). Se as buscas são poucas, a busca linear pode ser mais simples.
• Estrutura de dados: a busca binária funciona em arrays, mas se você precisar de inserções frequentes, outras estruturas como árvores de busca podem ser melhores.
• Tipos de dados: bsearch é genérica, mas exige cuidado com ponteiros e funções de comparação. Teste bem a função de comparação para evitar erros sutis.
• Overflow: no cálculo do meio, use esq + (dir - esq) / 2 para evitar overflow.
• Legibilidade: para fins didáticos, implementar manualmente pode ser útil, mas em código de produção, prefira bsearch se possível.

Lembre-se de sempre validar os limites dos arrays e considerar o caso de elementos repetidos. A busca binária tradicional retorna uma ocorrência arbitrária; se precisar da primeira ou última, você precisará de variações.

Referências

• cppreference: bsearch
• GNU C Library: Array Search Function
• Wikipedia: Binary search algorithm
• Wikipedia: Linear search
• IME-USP: Algoritmos de busca

Exercícios

1. Implemente uma função de busca linear que retorne a última ocorrência do valor em um array não ordenado. Teste com um array de exemplo.

Ver resposta

int busca_linear_ultima(int arr[], int n, int alvo) {
    for (int i = n-1; i >= 0; i--) {
        if (arr[i] == alvo) return i;
    }
    return -1;
}

Ver resposta

int busca_binaria_rec(int arr[], int esq, int dir, int alvo) {
    if (esq > dir) return -1;
    int meio = esq + (dir - esq) / 2;
    if (arr[meio] == alvo) return meio;
    if (arr[meio] < alvo) return busca_binaria_rec(arr, meio+1, dir, alvo);
    else return busca_binaria_rec(arr, esq, meio-1, alvo);
}

Ver resposta

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int compar_str(const void *a, const void *b) {
    return strcmp(*(const char **)a, *(const char **)b);
}

int main() {
    const char *nomes[] = {"ana", "bruno", "carla"};
    int n = sizeof(nomes)/sizeof(nomes[0]);
    const char *chave = "bruno";
    char **res = bsearch(&chave, nomes, n, sizeof(char *), compar_str);
    if (res) printf("Encontrado: %s\n", *res);
    else printf("Não encontrado\n");
    return 0;
}

Ver resposta

int busca_primeiro(int arr[], int n, int alvo) {
    int esq = 0, dir = n-1, res = -1;
    while (esq <= dir) {
        int meio = esq + (dir - esq)/2;
        if (arr[meio] == alvo) { res = meio; dir = meio - 1; }
        else if (arr[meio] < alvo) esq = meio + 1;
        else dir = meio - 1;
    }
    return res;
}

int busca_ultimo(int arr[], int n, int alvo) {
    int esq = 0, dir = n-1, res = -1;
    while (esq <= dir) {
        int meio = esq + (dir - esq)/2;
        if (arr[meio] == alvo) { res = meio; esq = meio + 1; }
        else if (arr[meio] < alvo) esq = meio + 1;
        else dir = meio - 1;
    }
    return res;
}

int contar_ocorrencias(int arr[], int n, int alvo) {
    int primeiro = busca_primeiro(arr, n, alvo);
    if (primeiro == -1) return 0;
    int ultimo = busca_ultimo(arr, n, alvo);
    return ultimo - primeiro + 1;
}

Ver resposta