CKTIS / C
Ricerca binaria e lower bound in C
La ricerca binaria dimezza ripetutamente un intervallo di ricerca ordinato. L’esempio implementa lower bound: l’indice del primo elemento non minore della chiave, oppure n se non esiste. Tratta i duplicati, l’input vuoto e il calcolo sicuro del punto medio.
Versione: C23; repository compiler flag, production runtime not attested
Sintassi
size_t lower_bound_int(const int *a, size_t n, int key);La ricerca binaria sceglie il punto medio di un intervallo ed elimina la metà che non può contenere il risultato cercato. La precondizione di input ordinato significa qui che a[0..n) è ordinato in modo non decrescente secondo lo stesso criterio di confronto usato dalla ricerca. La funzione non verifica questa condizione; con dati non ordinati il risultato può essere errato.
La funzione di esempio lower_bound_int implementa lower bound: restituisce il primo indice pos per cui a[pos] >= key, oppure n se non esiste. In presenza di duplicati, indica la prima occorrenza. Il solo indice non conferma che la chiave sia presente: usare il test pos < n && a[pos] == key. La valutazione con cortocircuito impedisce a questo test di leggere a[n].
Il ciclo mantiene l’intervallo semiaperto [lo, hi): gli elementi prima di lo sono minori di key, mentre quelli da hi a n non sono minori di key. L’istruzione hi = mid conserva un possibile primo risultato, mentre lo = mid + 1 salta un elemento troppo piccolo. L’espressione lo + (hi - lo) / 2 evita l’overflow dovuto alla somma degli estremi. Quando lo == hi, entrambi i limiti identificano il risultato.
Per n > 0, a deve fornire almeno n elementi validi, che non devono cambiare durante la ricerca. Per n == 0, questa implementazione accetta NULL e restituisce 0 senza leggere memoria. Su un array, il tempo è O(log n) per n >= 2 e lo spazio ausiliario è O(1); l’ordinamento precedente non è incluso. C23 è l’obiettivo delle opzioni del compilatore del repository, non un’attestazione dell’ambiente di esecuzione in produzione.
Esempi
#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;
}
Risultato
key=3 pos=1 found=1 key=4 pos=3 found=0 key=9 pos=4 found=0 empty pos=0
Il codice mostrato e il risultato dichiarato sono stati verificati in un ambiente isolato con il metodo registrato nella prova di verifica di questa versione esatta.