📚 Capítulo do curso: 10 — Vetores 1D (Arrays), Memória e Algoritmos de Busca/Ordenação da Especialização em Sistemas com C. Leia o capítulo antes de começar.

🔎 Miniprojeto C 10 — Busca Binária e Benchmark de Ordenação

Ordena um vetor com Bubble Sort e mede, na prática, quantas comparações a Busca Binária economiza em relação à Busca Linear.

🔗 Conectando com o Miniprojeto 07: lá você implementou um crivo de primos “na unha”, testando cada número individualmente porque ainda não existiam vetores. Agora, com arrays de verdade liberados pelo Capítulo 10, o Desafio de Extensão deste projeto te convida a voltar e reescrever aquele crivo como um Crivo de Eratóstenes real, marcando múltiplos num vetor — a diferença de desempenho entre força bruta e crivo é brutal.

🎯 Objetivos

• Implementar um algoritmo de ordenação (Bubble Sort) operando sobre um array de inteiros.
• Implementar a Busca Binária, entendendo por que ela exige um vetor previamente ordenado.
• Medir e comparar, na prática, o número de comparações da Busca Binária (O(log N)) contra o pior caso da Busca Linear (O(N)).
• Passar arrays como parâmetro de função (int vetor[]), fixando a diferença entre percorrer um array por índice e as demais formas de acesso que você verá em capítulos futuros.

📋 O problema

Você está construindo o núcleo de um motor de busca simplificado. Ele recebe um array fixo de pelo menos 10 números inteiros desordenados e precisa: ordená-los para permitir buscas eficientes, localizar um valor específico usando Busca Binária, e provar — com números reais — por que vale a pena pagar o custo de ordenar antes de buscar repetidamente.

O programa (main.c) deve:

1. Declarar um array fixo de pelo menos 10 inteiros, desordenado.
2. Ordená-lo em ordem crescente usando Bubble Sort.
3. Buscar um valor-alvo no array já ordenado usando Busca Binária, contando quantas comparações foram realmente feitas.
4. Calcular e imprimir o pior caso teórico de comparações da Busca Linear (N) e da Busca Binária (≈ log2(N) + 1), evidenciando por que a busca binária escala muito melhor à medida que N cresce.

graph LR
    A["Vetor desordenado\n(10+ inteiros)"] --> B["ordenar_bubble_sort()"]
    B --> C["Vetor ordenado"]
    C --> D["busca_binaria()\ne contagem de comparacoes"]
    D --> E["Relatorio:\nBinaria vs Linear\n(pior caso)"]

    style B fill:#0284c7,stroke:#38bdf8,color:#ffffff
    style D fill:#0d9488,stroke:#2dd4bf,color:#ffffff
    style E fill:#059669,stroke:#34d399,color:#ffffff

🧰 Ambiente

O mesmo do Miniprojeto 01: gcc 8 ou mais novo. No Windows, rode chcp 65001 se os emojis aparecerem quebrados.

Passo 1 — Compilar o esqueleto

🎯 Objetivo: partir de um código que compila e roda, antes de escrever qualquer linha.

⌨️ Faça: crie a pasta c_mini_10, salve o código abaixo como main.c e rode:

gcc -Wall -Wextra -Wpedantic -std=c17 main.c -o app
./app          # Linux/macOS
.\app.exe      # Windows (PowerShell)

📄 src/esqueleto.c

/*
 * Miniprojeto 10: Motor de Busca Binaria e Benchmark de Ordenacao
 * Capitulo 10: arrays, busca linear/binaria, ordenacao.
 */
#include <stdio.h>
#include <stdlib.h>

#define TAMANHO 10

void ordenar_bubble_sort(int vetor[], int tamanho) {
    (void)vetor; (void)tamanho; // stub: apague esta linha ao implementar
    // TODO 1: implemente o Bubble Sort classico com dois lacos aninhados.
    // Dica: se uma passada inteira nao trocar nenhum par, o vetor ja esta
    // ordenado (use uma flag "trocou" para interromper mais cedo).
}

void imprimir_vetor(const int vetor[], int tamanho) {
    (void)vetor; (void)tamanho; // stub: apague esta linha ao implementar
    // TODO 2: imprima o vetor no formato "[ v0 v1 v2 ... ]"
}

int busca_binaria(const int vetor[], int tamanho, int alvo) {
    (void)vetor; (void)tamanho; (void)alvo; // stub: apague esta linha ao implementar
    // TODO 3: implemente a busca binaria classica (inicio/fim/meio) e
    // retorne o indice do elemento encontrado, ou -1 se nao encontrado.
    return -1;
}

int contar_comparacoes_busca_binaria(const int vetor[], int tamanho, int alvo) {
    (void)vetor; (void)tamanho; (void)alvo; // stub: apague esta linha ao implementar
    // TODO 4: repita a logica da busca binaria, mas desta vez contando
    // quantas vezes o valor do meio foi comparado com o alvo.
    return 0;
}

int main(void) {
    int numeros[TAMANHO] = {45, 12, 78, 3, 91, 27, 56, 8, 63, 34};
    int alvo = 63;

    printf("Valor a buscar: %d\n", alvo);

    printf("Vetor original (desordenado): ");
    imprimir_vetor(numeros, TAMANHO);

    ordenar_bubble_sort(numeros, TAMANHO);

    printf("Vetor ordenado (Bubble Sort): ");
    imprimir_vetor(numeros, TAMANHO);

    // TODO 5: chame busca_binaria e contar_comparacoes_busca_binaria,
    // imprima o indice encontrado e o benchmark (linear vs binaria).

    return EXIT_SUCCESS;
}

✅ Checkpoint: zero avisos do gcc, e a saída é:

🖥️ Saída esperada:

Valor a buscar: 63
Vetor original (desordenado): Vetor ordenado (Bubble Sort): 

💡 (void)parametro;: as funções do esqueleto ainda são stubs (cascas vazias). Sem essas linhas, o gcc -Wextra avisaria unused parameter. Apague cada linha (void)... quando implementar a função correspondente.

As linhas Vetor original e Vetor ordenado saem vazias e coladas porque imprimir_vetor ainda não faz nada.

Passo 2 — Imprimir o vetor (TODO 2)

🎯 Objetivo: percorrer um array recebido como parâmetro (const int vetor[]).

⌨️ Faça: em imprimir_vetor, imprima [ , cada elemento seguido de espaço e ] com quebra de linha.

✅ Checkpoint: as duas linhas mostram [ 45 12 78 3 91 27 56 8 63 34 ]. Ainda são iguais, porque a ordenação não existe.

🧯 Se der errado: sizeof(vetor) dentro da função dá 8, não 40. Um array passado para função vira ponteiro, por isso o tamanho precisa vir como parâmetro.

Passo 3 — Bubble Sort (TODO 1)

🎯 Objetivo: ordenar no lugar, trocando vizinhos fora de ordem.

⌨️ Faça: dois for aninhados: o externo conta as passadas (i) e o interno compara vetor[j] com vetor[j + 1] até tamanho - 1 - i, trocando com uma variável temp. Use uma flag trocou e faça break se uma passada inteira não trocar nada.

✅ Checkpoint: Vetor ordenado (Bubble Sort): [ 3 8 12 27 34 45 56 63 78 91 ].

🧯 Se der errado: um número estranho aparece no vetor (lixo ou o 91 duplicado): o laço interno foi até j < tamanho e leu vetor[j + 1] fora do array.

Passo 4 — Busca binária e contagem (TODO 3, 4 e 5)

🎯 Objetivo: dividir o espaço de busca pela metade a cada comparação.

⌨️ Faça:

1. busca_binaria: com inicio = 0 e fim = tamanho - 1, enquanto inicio <= fim, calcule meio = inicio + (fim - inicio) / 2. Se achou, devolva meio; senão, mova inicio ou fim. Ao sair do laço, devolva -1.
2. contar_comparacoes_busca_binaria: a mesma lógica, incrementando um contador a cada meio examinado.
3. No main, imprima o índice encontrado e o benchmark: pior caso linear (N), pior caso binário e as comparações reais. Para o pior caso binário, conte quantas vezes é preciso dobrar 1 até alcançar N e some 1.

✅ Checkpoint: Valor 63 encontrado no indice 7., pior caso linear 10, pior caso binário 5 e 2 comparações reais. O primeiro meio é o índice 4 (valor 34), e o segundo já é o 7.

🧯 Se der errado: o programa trava: inicio ou fim não estão mudando, por exemplo com inicio = meio em vez de meio + 1.

Passo final — Conferir com o gabarito

🎯 Objetivo: validar a saída completa e o código de retorno.

✅ Checkpoint: a saída é esta, e o código de retorno é 0 (echo $? no Linux/macOS ou echo $LASTEXITCODE no PowerShell):

🖥️ Saída esperada:

====================================================
 ⚡ Motor de Busca Binaria e Benchmark de Ordenacao
====================================================
Vetor original (desordenado): [ 45 12 78 3 91 27 56 8 63 34 ]
Vetor ordenado (Bubble Sort): [ 3 8 12 27 34 45 56 63 78 91 ]

----------------------------------------------------
Valor 63 encontrado no indice 7.

--- Benchmark de comparacoes (N = 10) ---
Busca Linear  -> pior caso teorico: 10 comparacoes
Busca Binaria -> pior caso teorico: 5 comparacoes
Busca Binaria -> comparacoes reais nesta execucao: 2
====================================================

Só abra o gabarito depois de chegar até aqui:

/*
 * Miniprojeto 10: Motor de Busca Binaria e Benchmark de Ordenacao
 * Especializacao em Engenharia de Sistemas em C
 * Capitulo 10: arrays, busca linear/binaria, algoritmos de ordenacao.
 */
#include <stdio.h>
#include <stdlib.h>

#define TAMANHO 10

void ordenar_bubble_sort(int vetor[], int tamanho) {
    for (int i = 0; i < tamanho - 1; i++) {
        int trocou = 0;
        for (int j = 0; j < tamanho - 1 - i; j++) {
            if (vetor[j] > vetor[j + 1]) {
                int temp = vetor[j];
                vetor[j] = vetor[j + 1];
                vetor[j + 1] = temp;
                trocou = 1;
            }
        }
        if (!trocou) {
            break;
        }
    }
}

void imprimir_vetor(const int vetor[], int tamanho) {
    printf("[ ");
    for (int i = 0; i < tamanho; i++) {
        printf("%d ", vetor[i]);
    }
    printf("]\n");
}

int busca_binaria(const int vetor[], int tamanho, int alvo) {
    int inicio = 0;
    int fim = tamanho - 1;

    while (inicio <= fim) {
        int meio = inicio + (fim - inicio) / 2;
        if (vetor[meio] == alvo) {
            return meio;
        }
        if (vetor[meio] < alvo) {
            inicio = meio + 1;
        } else {
            fim = meio - 1;
        }
    }
    return -1;
}

int contar_comparacoes_busca_binaria(const int vetor[], int tamanho, int alvo) {
    int inicio = 0;
    int fim = tamanho - 1;
    int comparacoes = 0;

    while (inicio <= fim) {
        int meio = inicio + (fim - inicio) / 2;
        comparacoes++;
        if (vetor[meio] == alvo) {
            break;
        }
        if (vetor[meio] < alvo) {
            inicio = meio + 1;
        } else {
            fim = meio - 1;
        }
    }
    return comparacoes;
}

int comparacoes_pior_caso_binaria(int tamanho) {
    int comparacoes = 0;
    int alcance = 1;
    while (alcance < tamanho) {
        alcance *= 2;
        comparacoes++;
    }
    return comparacoes + 1;
}

int main(void) {
    int numeros[TAMANHO] = {45, 12, 78, 3, 91, 27, 56, 8, 63, 34};
    int alvo = 63;

    printf("====================================================\n");
    printf(" ⚡ Motor de Busca Binaria e Benchmark de Ordenacao\n");
    printf("====================================================\n");

    printf("Vetor original (desordenado): ");
    imprimir_vetor(numeros, TAMANHO);

    ordenar_bubble_sort(numeros, TAMANHO);

    printf("Vetor ordenado (Bubble Sort): ");
    imprimir_vetor(numeros, TAMANHO);

    int indice = busca_binaria(numeros, TAMANHO, alvo);
    int comparacoes_reais = contar_comparacoes_busca_binaria(numeros, TAMANHO, alvo);

    printf("\n----------------------------------------------------\n");
    if (indice != -1) {
        printf("Valor %d encontrado no indice %d.\n", alvo, indice);
    } else {
        printf("Valor %d nao encontrado no vetor.\n", alvo);
    }

    int pior_caso_linear = TAMANHO;
    int pior_caso_binaria = comparacoes_pior_caso_binaria(TAMANHO);

    printf("\n--- Benchmark de comparacoes (N = %d) ---\n", TAMANHO);
    printf("Busca Linear  -> pior caso teorico: %d comparacoes\n", pior_caso_linear);
    printf("Busca Binaria -> pior caso teorico: %d comparacoes\n", pior_caso_binaria);
    printf("Busca Binaria -> comparacoes reais nesta execucao: %d\n", comparacoes_reais);
    printf("====================================================\n");

    return EXIT_SUCCESS;
}

Por que isso importa: repare que busca_binaria e contar_comparacoes_busca_binaria implementam a mesma lógica, mas separadas — a segunda existe só para instrumentar (medir) a primeira sem poluir o código de produção com contadores. Esse padrão de “versão instrumentada para benchmark” é comum em engenharia de sistemas real.

🏆 Desafio

Volte ao Miniprojeto 07 e reescreva o crivo de primos como um Crivo de Eratóstenes real: declare um array int eh_primo[101], inicialize todas as posições com 1 (exceto os índices 0 e 1), e para cada número p de 2 até 100, se eh_primo[p] ainda for 1, marque todos os seus múltiplos (2p, 3p, 4p, ...) como eh_primo[multiplo] = 0. No fim, percorra o array e imprima todos os índices ainda marcados como primos. Compare mentalmente: o Miniprojeto 07 testava cada número individualmente (força bruta); o crivo elimina múltiplos em lote, e é muito mais rápido para gerar todos os primos até N.

✅ Checkpoint: o crivo até 100 encontra 25 primos, de 2 a 97, os mesmos que a versão por divisão de tentativa do Miniprojeto 07 acharia.

🧭 Navegação

📋 Projetos do curso de C | 📚 Teoria do Capítulo 10 | 🗂️ Hub de projetos