Base di conoscenzaCentro esami
ITItaliano
Scegli la lingua13

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.

Fonti