CodeUtility
Tornando o seu trabalho de dev mais simples!
Algoritmos C/C++

Busca binária em C e C++

Nesta lição, você vai buscar em um array ordenado em tempo O(log n) com um laço escrito à mão em C e com std::lower_bound em C++.

Introdução

A busca binária compara o valor procurado com o elemento do meio do intervalo de busca e descarta a metade que não pode contê-lo. Repetindo esse processo, o intervalo encolhe muito rápido, mas os dados de entrada precisam estar ordenados.

Pontos importantes

  • Teste com entradas vazias, com um único elemento, com valores repetidos e já ordenadas.
  • Primeiro faça funcionar corretamente, depois otimize.
  • Em código real, prefira as funções prontas da biblioteca padrão.

Visualizador de Busca binária em C e C++

O(log n)

Use Executar ou Passo para acompanhar cada comparação e movimento dos dados.

Exemplos de código C e C++

C
Executar →
main.c
#include <stdio.h>

int search(const int *values, int size, int target) {
    int low = 0;
    int high = size - 1;
    while (low <= high) {
        int middle = low + (high - low) / 2;
        if (values[middle] == target) return middle;
        if (values[middle] < target) low = middle + 1;
        else high = middle - 1;
    }
    return -1;
}

int main(void) {
    int values[] = {3, 7, 11, 16, 23, 28};
    printf("index=%d\n", search(values, 6, 23));
}
Resultado da execução
index=4
C++
Executar →
main.cpp
#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    std::vector values{3, 7, 11, 16, 23, 28};
    auto match = std::lower_bound(values.begin(), values.end(), 23);
    std::cout << "index="
              << std::distance(values.begin(), match) << '\n';
}
Resultado da execução
index=4

Comparação entre C e C++

Na versão em C, a posição do meio é calculada como low + (high - low) / 2 em vez de (low + high) / 2, para evitar estouro quando os índices são muito grandes. A cada comparação, low ou high passa para a metade restante. A versão em C++ usa std::lower_bound para achar a primeira posição que não é menor que o valor procurado. As duas têm complexidade O(log n).

C

Laços, ponteiros, tamanhos e buffers temporários são escritos explicitamente.

C++

Iteradores e algoritmos padrão separam o processamento da forma como os dados são guardados.

Exercícios práticos

Execute as duas versões e depois mude o código para observar a diferença de segurança que cada linguagem oferece.

  • Simule cada comparação no papel.
  • Teste com valores repetidos e com valores muito grandes e muito pequenos.
  • Meça o tempo do seu código e compare com a biblioteca padrão.

Pratique com um desafio

Use o conteúdo desta lição para resolver um problema real. Cada desafio roda no navegador, com testes instantâneos e uma revisão por IA.

Todos os desafios