Busca Binária¶

A busca binária descarta repetidamente metade de um intervalo de busca ordenado e com acesso aleatório. Ela não ordena a entrada.

Contrato¶

Pré-condição: values está ordenado em ordem não decrescente.
Saída: um índice que contém target, ou -1 se estiver ausente.
Quando existem valores duplicados, esta versão básica pode retornar qualquer índice correspondente.

static int binarySearch(int[] values, int target) {
    int low = 0;
    int high = values.length - 1;

    while (low <= high) {
        int middle = low + (high - low) / 2;
        int value = values[middle];
        if (value == target) return middle;
        if (value < target) low = middle + 1;
        else high = middle - 1;
    }
    return -1;
}

A expressão usada para o ponto médio evita o overflow da soma que pode ocorrer em (low + high) / 2.

Correção¶

Use o invariante: se o alvo ocorre, pelo menos uma ocorrência está no intervalo inclusivo [low, high]. A ordem dos elementos justifica descartar a metade que não pode conter o alvo. O intervalo diminui estritamente. Se ficar vazio, nenhuma ocorrência existe.

Complexidade¶

Cada iteração reduz o intervalo candidato à metade, resultando em tempo Θ(log n) no pior caso e espaço auxiliar Θ(1). Ordenar primeiro normalmente custaria Ω(n log n) e mudaria as posições; portanto, essa é uma decisão separada de pré-processamento.

Exercícios¶

Retorne o primeiro índice correspondente entre valores duplicados.
Implemente uma versão com intervalo semiaberto [low, high).
Declare o que falha se o array não estiver ordenado.