Base de conhecimentoCentro de Exames
PT · PTPortuguês (Portugal)
Escolher idioma13

CKTIS / C

Pesquisa binária e lower bound em C

A pesquisa binária reduz repetidamente para metade um intervalo de pesquisa ordenado. O exemplo implementa lower bound: o índice do primeiro elemento que não é inferior à chave, ou n se não existir. Abrange duplicados, entrada vazia e cálculo seguro do ponto médio.

Versão: C23; repository compiler flag, production runtime not attested

Sintaxe

size_t lower_bound_int(const int *a, size_t n, int key);

A pesquisa binária escolhe o ponto médio de um intervalo e descarta a metade que não pode conter o resultado procurado. A pré-condição de entrada ordenada significa aqui que a[0..n) está ordenado por ordem não decrescente, segundo a mesma comparação usada pela pesquisa. A função não verifica esta condição; uma entrada desordenada pode produzir um resultado incorreto.

A função de exemplo lower_bound_int implementa lower bound: devolve o primeiro índice pos para o qual a[pos] >= key, ou n se não existir nenhum. Havendo duplicados, indica a primeira ocorrência. O índice, por si só, não confirma a presença da chave: use o teste pos < n && a[pos] == key. A avaliação em curto-circuito impede que este teste leia a[n].

O ciclo mantém o intervalo semiaberto [lo, hi): os elementos anteriores a lo são menores do que key, e os elementos de hi até n não são menores do que key. A instrução hi = mid mantém um possível primeiro resultado, enquanto lo = mid + 1 ignora um elemento demasiado pequeno. A expressão lo + (hi - lo) / 2 evita o overflow ao somar os limites. Quando lo == hi, ambos os limites determinam o resultado.

Para n > 0, a tem de disponibilizar pelo menos n elementos válidos, que não podem ser alterados durante a pesquisa. Para n == 0, esta implementação aceita NULL e devolve 0 sem ler memória. Num array, o tempo é O(log n) para n >= 2 e o espaço auxiliar é O(1); a ordenação prévia não está incluída. C23 é o alvo das opções de compilação do repositório, não uma garantia sobre o ambiente de execução em produção.

Exemplos

#include <stddef.h>
#include <stdio.h>

static size_t lower_bound_int(const int *a, size_t n, int key)
{
    size_t lo = 0;
    size_t hi = n;

    while (lo < hi) {
        size_t mid = lo + (hi - lo) / 2;
        if (a[mid] < key) {
            lo = mid + 1;
        } else {
            hi = mid;
        }
    }
    return lo;
}

int main(void)
{
    const int a[] = {1, 3, 3, 7};
    const size_t n = sizeof a / sizeof a[0];
    const int keys[] = {3, 4, 9};

    for (size_t i = 0; i < sizeof keys / sizeof keys[0]; ++i) {
        size_t pos = lower_bound_int(a, n, keys[i]);
        int found = pos < n && a[pos] == keys[i];
        printf("key=%d pos=%zu found=%d\n", keys[i], pos, found);
    }
    printf("empty pos=%zu\n", lower_bound_int(NULL, 0, 3));
    return 0;
}

Resultado

key=3 pos=1 found=1
key=4 pos=3 found=0
key=9 pos=4 found=0
empty pos=0

O código apresentado e o resultado declarado foram verificados num ambiente isolado pelo método registado na prova de verificação desta versão exata.

Fontes