C Busca (bsearch)

Procurar é tão comum quanto ordenar: o caixa da lojinha procura o produto pelo código de barras, a professora procura o aluno na chamada, o programa procura uma palavra no dicionário. Se os dados estão bagunçados, o único jeito é olhar um por um. Se estão em ordem, dá para fazer como num dicionário de papel: abrir no meio e descartar metade a cada olhada. Nesta aula você vai escrever os dois jeitos à mão e depois usar o bsearch, a busca binária pronta da biblioteca padrão.

Esta aula usa Ordenação (qsort) e Ponteiros para Funções. Todos os programas foram compilados com o gcc 15.2 na máquina fictícia da Ana (usuária ana, computador notebook), na pasta ~/c, com o comando padrão do guia: gcc -std=c23 -Wall -Wextra arquivo.c -o programa.

A ideia: o dicionário de papel

Para achar "pêssego" num dicionário, ninguém lê desde a primeira página. Você abre mais ou menos no meio, vê que caiu no "l", e sabe que "pêssego" está depois: a primeira metade inteira foi descartada sem ser lida. Abre no meio do que sobrou, e assim por diante. Isso só funciona porque o dicionário está em ordem alfabética. Numa pilha de fichas bagunçadas, você teria de olhar ficha por ficha.

1. Busca linear: um por um

A busca mais simples olha cada item, do primeiro ao último, e para quando acha. Ela funciona com qualquer array, ordenado ou não:

#include <stdio.h>

int buscar(const int *v, int n, int procurado) {
    for (int i = 0; i < n; i++) {
        if (v[i] == procurado) {
            printf("  achou depois de olhar %d números\n", i + 1);
            return i;
        }
    }
    printf("  olhou os %d números e não achou\n", n);
    return -1;
}

int main(void) {
    int senhas[] = {42, 7, 93, 15, 61, 28, 84, 3, 50, 77};
    int n = sizeof senhas / sizeof senhas[0];

    printf("Procurando 28:\n");
    int pos = buscar(senhas, n, 28);
    printf("  posição: %d\n", pos);

    printf("Procurando 99:\n");
    pos = buscar(senhas, n, 99);
    printf("  posição: %d\n", pos);
    return 0;
}

$ gcc -std=c23 -Wall -Wextra linear.c -o linear
$ ./linear
Procurando 28:
  achou depois de olhar 6 números
  posição: 5
Procurando 99:
  olhou os 10 números e não achou
  posição: -1

int buscar(const int *v, int n, int procurado)

Recebe o array (o const promete só ler), quantos itens ele tem e o valor procurado. Devolve a posição onde achou.

if (v[i] == procurado) return i;

Achou: devolve a posição e sai da função na hora, sem olhar o resto.

return -1;

Se o laço acabou, olhou tudo e não achou. -1 nunca é uma posição válida, então serve de aviso "não está" (como o EOF do getchar).

Quando o item não está, a busca linear olha todos. Com 10 números, tudo bem. Com um milhão de produtos e um caixa que procura um código a cada segundo, é um milhão de comparações por cliente.

2. Busca binária à mão

Se o array estiver em ordem crescente, dá para fazer o jogo do dicionário. Duas variáveis marcam o pedaço do array onde o item ainda pode estar: ini (o começo) e fim (o fim). A cada passo, olha-se o item do meio:

• se for o procurado, acabou;
• se for menor que o procurado, o procurado só pode estar à direita: ini = meio + 1;
• se for maior, só pode estar à esquerda: fim = meio - 1.

Se ini passar de fim, o pedaço ficou vazio: o item não está no array.

#include <stdio.h>

int buscar(const int *v, int n, int procurado) {
    int ini = 0;
    int fim = n - 1;
    while (ini <= fim) {
        int meio = ini + (fim - ini) / 2;
        printf("  ini=%2d fim=%2d meio=%2d: v[meio] = %d\n", ini, fim, meio, v[meio]);
        if (v[meio] == procurado) {
            return meio;
        }
        if (v[meio] < procurado) {
            ini = meio + 1;
        } else {
            fim = meio - 1;
        }
    }
    return -1;
}

int main(void) {
    int v[] = {3, 7, 15, 28, 33, 37, 42, 50, 61, 64, 77, 84, 88, 93, 99};
    int n = sizeof v / sizeof v[0];

    printf("Procurando 37:\n");
    printf("  posição: %d\n", buscar(v, n, 37));
    printf("Procurando 40:\n");
    printf("  posição: %d\n", buscar(v, n, 40));
    return 0;
}

$ gcc -std=c23 -Wall -Wextra binaria.c -o binaria
$ ./binaria
Procurando 37:
  ini= 0 fim=14 meio= 7: v[meio] = 50
  ini= 0 fim= 6 meio= 3: v[meio] = 28
  ini= 4 fim= 6 meio= 5: v[meio] = 37
  posição: 5
Procurando 40:
  ini= 0 fim=14 meio= 7: v[meio] = 50
  ini= 0 fim= 6 meio= 3: v[meio] = 28
  ini= 4 fim= 6 meio= 5: v[meio] = 37
  ini= 6 fim= 6 meio= 6: v[meio] = 42
  posição: -1

int ini = 0; int fim = n - 1;

No começo, o array todo está em jogo: da posição 0 à última.

while (ini <= fim)

Enquanto o pedaço tiver pelo menos um item. Com ini == fim, sobra um item só, e ele ainda precisa ser olhado (foi o 42 na busca pelo 40).

int meio = ini + (fim - ini) / 2;

A posição do meio do pedaço. A divisão inteira joga fora a fração: de 0 a 14, o meio é 7; de 4 a 6, é 5. Por que não (ini + fim) / 2? Com arrays enormes, ini + fim pode passar do máximo do int; fim - ini nunca passa.

ini = meio + 1; / fim = meio - 1;

O + 1 e o - 1 tiram do jogo o próprio meio, que já foi olhado. Sem eles, o pedaço pode parar de encolher (veja Quando dá errado).

return -1;

Na busca pelo 40: depois do 42, fim virou 5 e ficou menor que ini (6). Não sobrou onde procurar.

37 está na posição 5
40 não está
3 está na posição 0
99 está na posição 14

#include <stdio.h>

int buscar(const int *v, int n, int procurado) {
    int ini = 0;
    int fim = n - 1;
    while (ini <= fim) {
        int meio = ini + (fim - ini) / 2;
        if (v[meio] == procurado) {
            return meio;
        }
        // COMPLETE: se v[meio] for menor que o procurado, descarte a metade
        // da esquerda (ini = meio + 1); senão, descarte a da direita
        // (fim = meio - 1). Depois, apague o break.
        break;
    }
    return -1;
}

int main(void) {
    int v[] = {3, 7, 15, 28, 33, 37, 42, 50, 61, 64, 77, 84, 88, 93, 99};
    int n = sizeof v / sizeof v[0];
    int procurados[] = {37, 40, 3, 99};
    for (int i = 0; i < 4; i++) {
        int pos = buscar(v, n, procurados[i]);
        if (pos >= 0) {
            printf("%d está na posição %d\n", procurados[i], pos);
        } else {
            printf("%d não está\n", procurados[i]);
        }
    }
    return 0;
}

#include <stdio.h>

int buscar(const int *v, int n, int procurado) {
    int ini = 0;
    int fim = n - 1;
    while (ini <= fim) {
        int meio = ini + (fim - ini) / 2;
        if (v[meio] == procurado) {
            return meio;
        }
        if (v[meio] < procurado) {
            ini = meio + 1;
        } else {
            fim = meio - 1;
        }
    }
    return -1;
}

int main(void) {
    int v[] = {3, 7, 15, 28, 33, 37, 42, 50, 61, 64, 77, 84, 88, 93, 99};
    int n = sizeof v / sizeof v[0];
    int procurados[] = {37, 40, 3, 99};
    for (int i = 0; i < 4; i++) {
        int pos = buscar(v, n, procurados[i]);
        if (pos >= 0) {
            printf("%d está na posição %d\n", procurados[i], pos);
        } else {
            printf("%d não está\n", procurados[i]);
        }
    }
    return 0;
}

Quantos passos?

Cada passo da busca binária corta o pedaço pela metade. Por isso o número de passos cresce muito devagar: quando o array dobra de tamanho, ela precisa de só um passo a mais.

(Os números da busca binária são quantas vezes dá para dividir o tamanho por 2 até sobrar 1, mais o último passo: o logaritmo de base 2, para quem já viu na escola.) Um bilhão de itens em 30 olhadas: é por isso que vale a pena manter os dados ordenados.

3. O bsearch: a busca binária pronta

A biblioteca padrão traz a busca binária pronta em <stdlib.h>: o bsearch (binary search, busca binária). Ele funciona com arrays de qualquer tipo, do mesmo jeito que o qsort, e usa o mesmo tipo de função de comparação:

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

int comparar(const void *a, const void *b) {
    int x = *(const int *)a;
    int y = *(const int *)b;
    return (x > y) - (x < y);
}

int main(void) {
    int v[] = {3, 7, 15, 28, 33, 37, 42, 50, 61, 64, 77, 84, 88, 93, 99};
    size_t n = sizeof v / sizeof v[0];
    int procurados[] = {37, 40};

    for (int i = 0; i < 2; i++) {
        int *achado = bsearch(&procurados[i], v, n, sizeof v[0], comparar);
        if (achado != NULL) {
            printf("%d está na posição %td\n", *achado, achado - v);
        } else {
            printf("%d não está no array\n", procurados[i]);
        }
    }
    return 0;
}

$ gcc -std=c23 -Wall -Wextra bsearch_int.c -o bsearch_int
$ ./bsearch_int
37 está na posição 5
40 não está no array

O protótipo é: void *bsearch(const void *chave, const void *base, size_t n, size_t tamanho, int (*comparar)(const void *, const void *));

int *achado = bsearch(…);

O bsearch devolve void *, que vira int * sozinho na atribuição (aula Ponteiro void*).

if (achado != NULL)

Usar o resultado sem esta conferência é o erro mais comum com o bsearch.

achado - v

Subtrair dois ponteiros do mesmo array dá a distância entre eles em itens: a posição (aula Ponteiros e Arrays). O resultado tem o tipo ptrdiff_t, que se imprime com %td.

*achado

O próprio item do array. Como é um ponteiro para dentro do array, dá até para mudar o item por ele.

4. Buscar em structs: a chave vem primeiro

O caixa da lojinha recebe um código e precisa do produto inteiro. O array é de Produto, mas a chave é só um int. Isso é permitido: o padrão do C garante que o bsearch chama a comparação sempre com a chave no primeiro parâmetro e um item do array no segundo. Então os dois parâmetros podem ser de tipos diferentes:

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

typedef struct {
    int codigo;
    char nome[20];
    int preco;
} Produto;

int por_codigo(const void *chave, const void *item) {
    int c = *(const int *)chave;
    const Produto *p = item;
    return (c > p->codigo) - (c < p->codigo);
}

int main(void) {
    const Produto loja[] = {
        {101, "arroz", 2590}, {105, "feijao", 899}, {230, "leite", 599},
        {231, "queijo", 4290}, {310, "cafe", 1890}, {402, "pao", 75},
    };
    size_t n = sizeof loja / sizeof loja[0];
    int pedidos[] = {230, 402, 999};

    for (int i = 0; i < 3; i++) {
        const Produto *p = bsearch(&pedidos[i], loja, n, sizeof loja[0], por_codigo);
        if (p != NULL) {
            printf("%d: %s, R$ %d,%02d\n", pedidos[i], p->nome, p->preco / 100, p->preco % 100);
        } else {
            printf("%d: não cadastrado\n", pedidos[i]);
        }
    }
    return 0;
}

$ gcc -std=c23 -Wall -Wextra codigos.c -o codigos
$ ./codigos
230: leite, R$ 5,99
402: pao, R$ 0,75
999: não cadastrado

int por_codigo(const void *chave, const void *item)

Os nomes dos parâmetros já dizem o que é cada um. O tipo continua o exigido (const void * nos dois).

int c = *(const int *)chave;

O primeiro é a chave: um int.

const Produto *p = item;

O segundo é um item do array: um Produto.

(c > p->codigo) - (c < p->codigo)

Compara o código procurado com o do produto. O array loja está em ordem crescente de código, o mesmo critério.

const Produto loja[]

Com const, o resultado também é const Produto *: só para ler.

Buscar textos: o & que todo mundo esquece

Num array de const char *, cada item é um ponteiro, e a função de comparação do qsort recebe ponteiros para esses ponteiros (aula Ordenação). Para usar a mesma função no bsearch, a chave precisa ter a mesma forma: o endereço de um const char *, ou seja, &procurado:

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

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

int main(void) {
    const char *turma[] = {"Rui", "Ana", "Lia", "Bruno", "Davi", "Bia", "Caio"};
    size_t n = sizeof turma / sizeof turma[0];

    qsort(turma, n, sizeof turma[0], por_nome);

    const char *procurados[] = {"Davi", "Zeca"};
    for (int i = 0; i < 2; i++) {
        const char **achado = bsearch(&procurados[i], turma, n, sizeof turma[0], por_nome);
        if (achado != NULL) {
            printf("%s está na chamada, número %td\n", *achado, achado - turma + 1);
        } else {
            printf("%s não é desta turma\n", procurados[i]);
        }
    }
    return 0;
}

$ gcc -std=c23 -Wall -Wextra nomes_busca.c -o nomes_busca
$ ./nomes_busca
Davi está na chamada, número 5
Zeca não é desta turma

Depois do qsort, a turma fica Ana, Bia, Bruno, Caio, Davi, Lia, Rui, e o Davi é o número 5 da chamada (a posição 4, mais 1). O resultado do bsearch é um const char **: um ponteiro para o item do array, que por sua vez aponta para o nome; por isso *achado é o nome.

5. Itens repetidos: qual deles o bsearch acha?

Se o valor aparece várias vezes, o padrão do C diz que o bsearch pode devolver qualquer um deles. Para saber onde começam os repetidos (ou quantos são), escreva uma busca binária que procura a primeira posição com um valor maior ou igual ao procurado:

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

int comparar(const void *a, const void *b) {
    int x = *(const int *)a;
    int y = *(const int *)b;
    return (x > y) - (x < y);
}

// Devolve a posição do primeiro item que é >= procurado (ou n, se não houver)
size_t primeiro_maior_igual(const int *v, size_t n, int procurado) {
    size_t ini = 0;
    size_t fim = n;
    while (ini < fim) {
        size_t meio = ini + (fim - ini) / 2;
        if (v[meio] < procurado) {
            ini = meio + 1;
        } else {
            fim = meio;
        }
    }
    return ini;
}

int main(void) {
    int notas[] = {5, 6, 7, 7, 7, 7, 8, 9, 10};
    size_t n = sizeof notas / sizeof notas[0];
    int sete = 7;

    int *qualquer = bsearch(&sete, notas, n, sizeof notas[0], comparar);
    printf("bsearch achou um 7 na posição %td\n", qualquer - notas);

    size_t ini = primeiro_maior_igual(notas, n, 7);
    size_t fim = primeiro_maior_igual(notas, n, 8);
    printf("os 7 vão da posição %zu à %zu: %zu notas 7\n", ini, fim - 1, fim - ini);
    printf("um 6 novo entraria na posição %zu\n", primeiro_maior_igual(notas, n, 6));
    return 0;
}

$ gcc -std=c23 -Wall -Wextra primeiro.c -o primeiro
$ ./primeiro
bsearch achou um 7 na posição 4
os 7 vão da posição 2 à 5: 4 notas 7
um 6 novo entraria na posição 1

size_t fim = n;

Aqui o pedaço em jogo é de ini até fim - 1 (o fim fica fora). Assim, a resposta pode ser n: "todos são menores; o lugar é depois do último".

if (v[meio] < procurado) ini = meio + 1;

O meio é pequeno demais: a resposta está à direita dele.

else fim = meio;

O meio já serve (é maior ou igual), mas pode haver um anterior que também sirva: guarda o meio como fim e continua procurando à esquerda. Não há return no meio do laço: ele só para quando ini == fim.

primeiro_maior_igual(notas, n, 8) - primeiro_maior_igual(notas, n, 7)

O primeiro 8 menos o primeiro 7: quantos 7 existem. Sem olhar um por um.

um 6 novo entraria na posição 1

A mesma função diz onde inserir um valor para o array continuar ordenado.

O bsearch achou o 7 da posição 4, que é um dos do meio, não o primeiro. Essa posição pode mudar de uma biblioteca para outra: não escreva programas que dependam dela.

Formas diferentes e qual usar

Quando dá errado

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

int comparar(const void *a, const void *b) {
    int x = *(const int *)a;
    int y = *(const int *)b;
    return (x > y) - (x < y);
}

int main(void) {
    int senhas[] = {42, 7, 93, 15, 61, 28, 84, 3, 50, 77};
    size_t n = sizeof senhas / sizeof senhas[0];
    int procurado = 3;

    int *achado = bsearch(&procurado, senhas, n, sizeof senhas[0], comparar);
    printf("3: %s\n", achado != NULL ? "achei" : "não está");
    return 0;
}

$ gcc -std=c23 -Wall -Wextra nao_ordenado.c -o nao_ordenado
$ ./nao_ordenado
3: não está

    int procurado = 40;
    int *achado = bsearch(&procurado, v, n, sizeof v[0], comparar);
    printf("Achei o %d\n", *achado);

$ gcc -std=c23 -Wall -Wextra sem_null.c -o sem_null
$ ./sem_null
Falha de segmentação     (imagem do núcleo gravada) ./sem_null

    const char *procurado = "Davi";
    const char **achado = bsearch(procurado, turma, n, sizeof turma[0], por_nome);

$ gcc -std=c23 -Wall -Wextra sem_endereco.c -o sem_endereco
$ ./sem_endereco
Falha de segmentação     (imagem do núcleo gravada) ./sem_endereco

        if (v[meio] < procurado) {
            ini = meio;          // faltou o + 1
        } else {
            fim = meio;          // faltou o - 1
        }

$ gcc -std=c23 -Wall -Wextra infinito.c -o infinito
$ timeout 3 ./infinito; echo "código: $?"
37 está na posição 5
código: 124

Referência rápida

Exercícios

Missão final: o leitor de código de barras

Loja com 6 produtos
230: leite, R$ 5,99
402: pao, R$ 0,75
999: não cadastrado

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

typedef struct {
    int codigo;
    char nome[20];
    int preco;
} Produto;

int por_codigo(const void *chave, const void *item) {
    // COMPLETE: chave aponta para um int (o código procurado) e item
    // aponta para um Produto do array. Compare o código procurado com
    // p->codigo e devolva negativo, zero ou positivo.
    (void)chave;
    (void)item;
    return 0;
}

int main(void) {
    // A loja está em ordem crescente de código: o bsearch precisa disso
    const Produto loja[] = {
        {101, "arroz", 2590}, {105, "feijao", 899}, {230, "leite", 599},
        {231, "queijo", 4290}, {310, "cafe", 1890}, {402, "pao", 75},
    };
    size_t n = sizeof loja / sizeof loja[0];
    printf("Loja com %zu produtos\n", n);
    int codigo;

    while (scanf("%d", &codigo) == 1) {
        const Produto *p = NULL; // COMPLETE: procure o código na loja com bsearch
        if (p != NULL) {
            printf("%d: %s, R$ %d,%02d\n", codigo, p->nome, p->preco / 100, p->preco % 100);
        } else {
            printf("%d: não cadastrado\n", codigo);
        }
    }
    return 0;
}

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

typedef struct {
    int codigo;
    char nome[20];
    int preco;
} Produto;

int por_codigo(const void *chave, const void *item) {
    int c = *(const int *)chave;
    const Produto *p = item;
    return (c > p->codigo) - (c < p->codigo);
}

int main(void) {
    // A loja está em ordem crescente de código: o bsearch precisa disso
    const Produto loja[] = {
        {101, "arroz", 2590}, {105, "feijao", 899}, {230, "leite", 599},
        {231, "queijo", 4290}, {310, "cafe", 1890}, {402, "pao", 75},
    };
    size_t n = sizeof loja / sizeof loja[0];
    printf("Loja com %zu produtos\n", n);
    int codigo;

    while (scanf("%d", &codigo) == 1) {
        const Produto *p = bsearch(&codigo, loja, n, sizeof loja[0], por_codigo);
        if (p != NULL) {
            printf("%d: %s, R$ %d,%02d\n", codigo, p->nome, p->preco / 100, p->preco % 100);
        } else {
            printf("%d: não cadastrado\n", codigo);
        }
    }
    return 0;
}

Depois de cumprir a missão, troque a entrada por outros códigos (101, 310, 231) e veja o caixa achar cada um em no máximo 3 passos. Com uma loja de 1 milhão de produtos, seriam 20.

Resumo

• A busca linear olha um por um; funciona com qualquer array, mas, quando o item não está, olha todos.
• A busca binária precisa do array ordenado: olha o meio e descarta metade a cada passo (ini = meio + 1 ou fim = meio - 1). Um milhão de itens em 20 passos.
• bsearch(&chave, v, n, sizeof v[0], comparar) é a busca binária pronta: devolve um ponteiro para o item achado ou NULL. Confira sempre o NULL; a posição é p - v.
• A comparação do bsearch recebe a chave primeiro, e ela pode ser de outro tipo (um código, para achar um Produto). O array precisa estar ordenado pelo mesmo critério.
• Num array de const char *, passe &procurado, para a chave ter a mesma forma dos itens.
• Com repetidos, o bsearch acha um qualquer; para o primeiro, ou para o lugar de inserir, use a busca "primeiro maior ou igual".