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.