Fundamentos da Busca Binária

A busca binária é um algoritmo otimizado para loaclizar elementos em arranjos ordenados. Além da busca exata, o método é amplamente utilizado para idantificar pontos de transição ou divisão em coleções, mesmo quando há elementos duplicados. A premissa básica envolve a redução do espaço de busca pela metade a cada iteração, partindo do princípio de que o alvo está contido no intervalo fechado [inicio, fim].

Padrões de Divisão de Intervalo

Para evitar ambiguidades e erros de off-by-one, a busca pode ser sistematizada em dois padrões principais. Ambos utilizam a condição de laço inicio < fim e terminam quando inicio == fim, garantindo a convergência em tempo O(log n).

Padrão 1: Atualização à Esquerda

Neste modelo, o intervalo é particionado em [inicio, meio] e [meio + 1, fim]. O ponto médio é calculado sem acréscimos, e as atualizações seguem as regras fim = meio ou inicio = meio + 1. É ideal quando a condição de verificação direciona a resposta para a metade esquerda.

int buscaPadraoUm(int inicio, int fim) {
    while (inicio < fim) {
        int meio = inicio + (fim - inicio) / 2;
        if (verificar(meio)) {
            inicio = meio + 1;
        } else {
            fim = meio;
        }
    }
    return inicio;
}

Padrão 2: Atualização à Direita

Aqui, o intervalo é fracionado em [inicio, meio - 1] e [meio, fim]. Neste caso, o cálculo do meio exige um acréscimo de 1 (meio = inicio + (fim - inicio + 1) / 2) para evitar laços infinitos. As atualizações são fim = meio - 1 ou inicio = meio. Aplica-se quando a condição empurra a solução para a metade direita.

int buscaPadraoDois(int inicio, int fim) {
    while (inicio < fim) {
        int meio = inicio + (fim - inicio + 1) / 2;
        if (verificar(meio)) {
            fim = meio - 1;
        } else {
            inicio = meio;
        }
    }
    return inicio;
}

A Prevenção de Laços Infinitos

O acréscimo de +1 no Padrão 2 é uma salvaguarda crítica. Se o espaço de busca for reduzido a dois elementos (ex: inicio = 0 e fim = 1), o cálculo padrão de meio resultaria em 0. Caso a lógica determine inicio = meio, o intervalo jamais encolherá, gerando um ciclo infinito. Ao deslocar o meio para 1, garantimos que a fronteira direita seja avaliada e o limite superior seja efetivamente reduzido.

Implementações Práticas

A aplicação destes padrões simplifica a resolução de problemas clássicos de fronteira, dispensando o retorno de valores intermediários e focando na contração sistemática do intervalo até restar um único elemento.

Busca Padrão por Valor Exato

int buscarExato(const std::vector<int>& arr, int alvo) {
    int ini = 0, fim = arr.size() - 1;
    while (ini <= fim) {
        int meio = ini + (fim - ini) / 2;
        if (arr[meio] == alvo) return meio;
        if (arr[meio] < alvo) ini = meio + 1;
        else fim = meio - 1;
    }
    return -1;
}</int>

Localização da Primeira Ocorrência

Encontrar o índice do primeiro elemento maior ou igual ao alvo requer que a busca continue na metade esquerda mesmo após uma correspondência, utilizando o Padrão 1.

int primeiraOcorrencia(const std::vector<int>& arr, int alvo) {
    int ini = 0, fim = arr.size() - 1;
    while (ini < fim) {
        int meio = ini + (fim - ini) / 2;
        if (arr[meio] < alvo)
            ini = meio + 1;
        else
            fim = meio;
    }
    return (arr[ini] == alvo) ? ini : -1;
}</int>

Localização da Última Ocorrência

Para o último elemento menor ou igual ao alvo, a busca deve convergir para a direita, aplicando o Padrão 2.

int ultimaOcorrencia(const std::vector<int>& arr, int alvo) {
    int ini = 0, fim = arr.size() - 1;
    while (ini < fim) {
        int meio = ini + (fim - ini + 1) / 2;
        if (arr[meio] > alvo)
            fim = meio - 1;
        else
            ini = meio;
    }
    return (arr[ini] == alvo) ? ini : -1;
}</int>

Cálculo da Raiz Quadrada Inteira

A raiz inteira de um número x é o maior inteiro k tal que k * k <= x. Se meio * meio > x, a resposta está à esquerda; caso contrário, à direita.

int raizQuadradaInteira(int x) {
    int ini = 0, fim = x;
    while (ini < fim) {
        long long meio = ini + (fim - ini + 1) / 2;
        if (meio > x / meio)
            fim = meio - 1;
        else
            ini = meio;
    }
    return ini;
}