Introdução à Busca Binária em Problemas de Programação Competitiva

A busca binária é um algoritmo fundamental amplamente utilizado na programação competitiva devido à sua eficiência (complexidade de tempo logarítmica O(log N)). Este artigo explora diversas aplicações da busca binária em problemas comuns, desde a localização de elementos até a contagem de ocorrências e o processamento de consultas em sequências.

1. Encontrando Elementos Comuns em Duas Listas Ordenadas (P1571 Olhos Vermelhos da Medusa)

O primeiro desafio consiste em identificar e listar elementos de uma sequência que também estão presentes em outra sequência, que pode ser previamente ordenada para otimizar a busca. Para cada elemento da primeira sequência, verificamos sua existência na segunda, mantendo a ordem original da primeira.

Método de Implementação

Para resolver este problema de forma eficiente, a estratégia é ordenar a segunda lista de números. Em seguida, para cada número da primeira lista, realizamos uma busca binária na segunda lista ordenada. Se um número for encontrado, ele é adicionado à saída.

Código C++

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits> // Para INT_MIN, INT_MAX

// Função de busca binária para encontrar um valor em um vetor ordenado.
// Retorna o índice do elemento se encontrado, -1 caso contrário.
int buscarElemento(const std::vector<int>& arrOrdenado, int valor) {
    int esq = 0; // Início do intervalo de busca
    int dir = arrOrdenado.size() - 1; // Fim do intervalo de busca

    while (esq <= dir) {
        int meio = esq + (dir - esq) / 2;
        if (arrOrdenado[meio] == valor) {
            return meio; // Elemento encontrado
        } else if (arrOrdenado[meio] < valor) {
            esq = meio + 1;
        } else {
            dir = meio - 1;
        }
    }
    return -1; // Elemento não encontrado
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    std::cout.tie(NULL);

    int n, m;
    std::cin >> n >> m;

    std::vector<int> listaA(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> listaA[i];
    }

    std::vector<int> listaB(m);
    for (int i = 0; i < m; ++i) {
        std::cin >> listaB[i];
    }

    // Ordena a lista B para permitir a busca binária eficiente
    std::sort(listaB.begin(), listaB.end());

    for (int i = 0; i < n; ++i) {
        if (buscarElemento(listaB, listaA[i]) != -1) {
            std::cout << listaA[i] << ' ';
        }
    }
    std::cout << std::endl;

    return 0;
}

2. Localizando a Primeira Ocorrência em um Array Ordenado (P2249 【Fundamentos 13.Ex1】Busca)

Este problema pede para encontrar o índice da primeira ocorrência de um determinado valor em um array ordenado. É uma variação comum da busca binária, onde precisamos garantir que, mesmo que o valor apareça múltiplas vezes, o índice retornado seja o do primeiro.

Análise de Erro Comum: 'Segmentation Fault'

Durante a implementação, um erro frequente em C++ é o "Segmentation fault with invalid memory reference" (erro de segmentação com referência de memória inválida). Isso geralmente ocorre quando o programa tenta acessar uma área de memória à qual não tem permissão, como ao exceder os limites de um array alocado. No contexto de problemas de programação, a causa mais comum é um array declarado com tamanho insuficiente para os dados de entrada, levando a acessos fora dos limites quando o índice excede a capacidade real do array.

Método de Implementação

Utilizamos uma busca binária modificada para localizar a primeira ocorrência. A ideia é, ao encontrar uma correspondência, continuar a busca na metade esquerda para ver se existe uma ocorrência ainda mais à esquerda.

Código C++ Corrigido

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

// Função de busca binária para encontrar a primeira ocorrência de um valor
// em um vetor ordenado, retornando seu índice (1-based) ou -1 se não encontrado.
int buscarPrimeiraOcorrencia(const std::vector<int>& arr, int valor) {
    int esq = 0; // Início do intervalo de busca (0-based)
    int dir = arr.size() - 1; // Fim do intervalo de busca (0-based)
    int resultado_idx = -1;

    while (esq <= dir) {
        int meio = esq + (dir - esq) / 2;
        if (arr[meio] == valor) {
            resultado_idx = meio; // Armazena este índice como possível resposta
            dir = meio - 1;       // Tenta encontrar uma ocorrência ainda mais à esquerda
        } else if (arr[meio] < valor) {
            esq = meio + 1;
        } else {
            dir = meio - 1;
        }
    }
    return resultado_idx != -1 ? resultado_idx + 1 : -1; // Retorna 1-based index
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    std::cout.tie(NULL);

    int n;
    std::cin >> n; // Tamanho do array

    std::vector<int> dados(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> dados[i];
    }

    int m;
    std::cin >> m; // Número de consultas

    for (int i = 0; i < m; ++i) {
        int consulta_valor;
        std::cin >> consulta_valor;
        std::cout << buscarPrimeiraOcorrencia(dados, consulta_valor) << ' ';
    }
    std::cout << std::endl;

    return 0;
}

3. Minimizar a Diferença Absoluta (P1678 Voluntariado para o Vestibular)

O problema consiste em, para cada aluno, encontrar a universidade cuja pontuação de corte é a mais próxima de sua própria pontuação. O objetivo é somar todas essas diferenças mínimas.

Método de Implementação

Primeiro, as pontuações de corte das universidades são ordenadas. Para cada pontuação de aluno, utilizamos a função std::lower\_bound para encontrar a primeira universidade cuja pontuação de corte é maior ou igual à pontuação do aluno. Em seguida, comparamos a diferença absoluta com esta universidade e, se houver, com a universidade imediatamente anterior na lista ordenada, escolhendo a menor diferença.

Código C++

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath> // Para std::abs

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    std::cout.tie(NULL);

    int num_universidades, num_alunos;
    std::cin >> num_universidades >> num_alunos;

    std::vector<int> cortes_universidades(num_universidades);
    for (int i = 0; i < num_universidades; ++i) {
        std::cin >> cortes_universidades[i];
    }

    std::sort(cortes_universidades.begin(), cortes_universidades.end());

    long long soma_diferencas = 0;
    for (int i = 0; i < num_alunos; ++i) {
        int pontuacao_aluno;
        std::cin >> pontuacao_aluno;

        // Encontra o iterador para o primeiro elemento >= pontuacao_aluno
        auto it = std::lower_bound(cortes_universidades.begin(), cortes_universidades.end(), pontuacao_aluno);

        long long menor_diferenca;

        if (it == cortes_universidades.begin()) {
            // Se o aluno é menor ou igual ao menor corte, a única opção é o primeiro
            menor_diferenca = std::abs(pontuacao_aluno - *it);
        } else if (it == cortes_universidades.end()) {
            // Se o aluno é maior que todos os cortes, a única opção é o último
            menor_diferenca = std::abs(pontuacao_aluno - cortes_universidades.back());
        } else {
            // O aluno está entre dois cortes ou igual a um deles
            long long diff_direita = std::abs(pontuacao_aluno - *it);
            long long diff_esquerda = std::abs(pontuacao_aluno - *(--it)); // Move o iterador para o elemento anterior
            menor_diferenca = std::min(diff_direita, diff_esquerda);
        }
        soma_diferencas += menor_diferenca;
    }

    std::cout << soma_diferencas << "\n";

    return 0;
}

4. Consultando o Índice Original de Elementos Ordenados (P1918 Boliche)

Neste problema, cada "bola" (representando um valor) possui um ID único que indica sua posição original. Precisamos ser capazes de encontrar o ID original de uma bola dado seu valor, após as bolas serem reordenadas por valor.

Método de Implementação

Para manter a associação entre o valor da bola e seu ID original, definimos uma estrutura de dados que armazena ambos. Criamos um vetor dessas estruturas e o ordenamos com base nos valores das bolas. Em seguida, implementamos uma busca binária para encontrar uma bola com um valor específico e retornar seu ID original.

Código C++

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

// Estrutura para armazenar o valor da bola e seu ID original
struct Bola {
    int id_original;
    int valor;
};

// Função de comparação para ordenar as bolas pelo valor
bool compararBolas(const Bola& a, const Bola& b) {
    return a.valor < b.valor;
}

// Função de busca binária para encontrar o ID original de uma bola por seu valor
// Retorna o ID original se encontrada, 0 caso contrário (se o problema permite 0 como não encontrado)
int buscarIdBola(const std::vector<Bola>& bolas_ordenadas, int valor_procurado) {
    int esq = 0;
    int dir = bolas_ordenadas.size() - 1;

    while (esq <= dir) {
        int meio = esq + (dir - esq) / 2;
        if (bolas_ordenadas[meio].valor == valor_procurado) {
            return bolas_ordenadas[meio].id_original;
        } else if (bolas_ordenadas[meio].valor < valor_procurado) {
            esq = meio + 1;
        } else {
            dir = meio - 1;
        }
    }
    return 0; // Não encontrado
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    std::cout.tie(NULL);

    int n; // Número de bolas
    std::cin >> n;

    std::vector<Bola> bolas(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> bolas[i].valor;
        bolas[i].id_original = i + 1; // IDs são 1-based
    }

    std::sort(bolas.begin(), bolas.end(), compararBolas);

    int m; // Número de consultas
    std::cin >> m;

    for (int i = 0; i < m; ++i) {
        int op;
        std::cin >> op;
        std::cout << buscarIdBola(bolas, op) << "\n";
    }

    return 0;
}

5. Contagem de Pares com Diferença Fixa (P1102 Pares A-B)

O problema é encontrar o número de pares (A, B) em um array tal que A - B = C, onde C é uma constante dada. Isso pode ser reescrito como A = B + C ou B = A - C.

Método de Implementação

A abordagem eficiente envolve ordenar o array primeiro. Para cada elemento A no array, buscmaos quantos elementos B existem tal que B = A - C. As funções std::lower\_bound e std::upper\_bound são ideais para essa tarefa. lower\_bound retorna um iterador para a primeira ocorrência do valor (ou onde ele deveria ser inserido para manter a ordem), e upper\_bound retorna um iterador para o primeiro elemento *maior* que o valor. A diferença entre esses dois iteradores nos dá o número de ocorrências do valor.

Código C++

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    std::cout.tie(NULL);

    int n; // Número de elementos
    long long c; // Constante C
    std::cin >> n >> c;

    std::vector<long long> elementos(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> elementos[i];
    }

    std::sort(elementos.begin(), elementos.end());

    long long contador_pares = 0;
    for (int i = 0; i < n; ++i) {
        long long valor_a = elementos[i];
        long long valor_b_alvo = valor_a - c; // Queremos encontrar B tal que B = A - C

        // Encontra o início do intervalo de ocorrências de valor_b_alvo
        auto it_lower = std::lower_bound(elementos.begin(), elementos.end(), valor_b_alvo);
        // Encontra o fim do intervalo de ocorrências de valor_b_alvo
        auto it_upper = std::upper_bound(elementos.begin(), elementos.end(), valor_b_alvo);

        // A diferença entre os iteradores dá o número de ocorrências
        contador_pares += (it_upper - it_lower);
    }

    std::cout << contador_pares << "\n";

    return 0;
}

6. Processamento de Consultas em Sequência com Offset Global (B3799 [NICA #1] Sequência)

Este problema envolve uma sequência de números e dois tipos de consultas: 1. Adicionar um valor k a um offset global, que afeta todos os elementos da sequência. 2. Calcular a soma de todos os elementos a\[i\] (após aplicar o offset global) que são maiores ou iguais a zero.

Método de Implementação

Como o offset é global, não precisamos modificar cada elemento individualmente. Podemos aplicar o offset no momento da consulta tipo 2. 1. **Pré-processamento:** Ordene o array de elementos e calcule os prefix sums (somas acumuladas) para consultas eficientes de soma em intervalos. 2. **Consulta Tipo 1 (Adicionar offset):** Simplesmente atualize uma variável global offset\_acumulado. 3. **Consulta Tipo 2 (Calcular soma):** * Para cada elemento a\[i\], a condição a\[i\] + offset\_acumulado >= 0 precisa ser satisfeita. Isso é equivalente a a\[i\] >= -offset\_acumulado. * Use std::lower\_bound no array ordenado para encontrar o primeiro elemento a\[i\] que satisfaz a\[i\] >= -offset\_acumulado. Isso nos dá um ponto de corte. * Calcule a soma dos elementos do ponto de corte até o final do array usando os prefix sums. * Para os elementos selecionados, adicione o offset\_acumulado a cada um e some. Isso pode ser feito como (soma\_dos\_elementos\_originais\_no\_intervalo) + (numero\_de\_elementos\_no\_intervalo \* offset\_acumulado).

Código C++

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric> // Para std::accumulate (se necessário, mas prefix sums são manuais aqui)

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    std::cout.tie(NULL);

    int n_elementos; // Número de elementos na sequência
    int q_consultas; // Número de consultas
    std::cin >> n_elementos >> q_consultas;

    std::vector<long long> sequencia(n_elementos);
    for (int i = 0; i < n_elementos; ++i) {
        std::cin >> sequencia[i];
    }

    std::sort(sequencia.begin(), sequencia.end());

    std::vector<long long> prefix_sums(n_elementos + 1, 0);
    for (int i = 0; i < n_elementos; ++i) {
        prefix_sums[i + 1] = prefix_sums[i] + sequencia[i];
    }

    long long offset_global = 0;

    while (q_consultas--) {
        int tipo_consulta;
        std::cin >> tipo_consulta;

        if (tipo_consulta == 1) {
            long long k;
            std::cin >> k;
            offset_global += k;
        } else {
            // Consulta tipo 2: Somar elementos a[i] + offset_global >= 0
            // Equivalente a a[i] >= -offset_global

            // Encontra o primeiro elemento que satisfaz a condição
            auto it = std::lower_bound(sequencia.begin(), sequencia.end(), -offset_global);
            
            int indice_inicio_soma = std::distance(sequencia.begin(), it); // 0-based index

            if (indice_inicio_soma == n_elementos) {
                // Todos os elementos são menores que -offset_global, então a soma é 0
                std::cout << 0 << "\n";
            } else {
                long long soma_originais_intervalo = prefix_sums[n_elementos] - prefix_sums[indice_inicio_soma];
                long long num_elementos_no_intervalo = n_elementos - indice_inicio_soma;
                
                long long soma_total = soma_originais_intervalo + (num_elementos_no_intervalo * offset_global);
                std::cout << soma_total << "\n";
            }
        }
    }

    return 0;
}