KennisbankExamencentrum
NL · NLNederlands (Nederland)
Taal kiezen13

CKTIS / C

Binair zoeken en lower bound in C

Binair zoeken halveert herhaaldelijk een gesorteerd zoekbereik. Het voorbeeld implementeert lower bound: de index van het eerste element dat niet kleiner is dan de sleutel, of n als dat element ontbreekt. Het behandelt duplicaten, lege invoer en een veilige berekening van het midden.

Versie: C23; repository compiler flag, production runtime not attested

Syntax

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

Binair zoeken kiest het midden van een bereik en verwerpt de helft die het gezochte resultaat niet kan bevatten. De voorwaarde dat de invoer gesorteerd is betekent hier dat a[0..n) niet-aflopend is gesorteerd volgens dezelfde vergelijking als bij het zoeken. De functie controleert deze voorwaarde niet; bij ongesorteerde invoer kan het resultaat onjuist zijn.

De voorbeeldfunctie lower_bound_int implementeert lower bound: ze retourneert de eerste index pos waarvoor a[pos] >= key geldt, of n als die index niet bestaat. Bij duplicaten wijst de functie de eerste voorkomst aan. De index alleen bevestigt niet dat de sleutel aanwezig is: gebruik de test pos < n && a[pos] == key. Door kortsluitevaluatie leest deze test a[n] niet.

De lus houdt het halfopen bereik [lo, hi) bij: elementen vóór lo zijn kleiner dan key, en elementen vanaf hi tot n zijn niet kleiner dan key. De instructie hi = mid behoudt een mogelijk eerste resultaat, terwijl lo = mid + 1 een te klein element overslaat. De expressie lo + (hi - lo) / 2 voorkomt overflow bij het optellen van de grenzen. Wanneer lo == hi, bepalen beide grenzen het resultaat.

Voor n > 0 moet a ten minste n geldige elementen bevatten; deze mogen tijdens het zoeken niet veranderen. Voor n == 0 accepteert deze implementatie NULL en retourneert ze 0 zonder geheugen te lezen. Voor een array is de tijd O(log n) bij n >= 2 en het extra geheugengebruik O(1); vooraf sorteren is niet inbegrepen. C23 is het doel van de compileropties van de repository, geen bevestiging van de productie-runtimeomgeving.

Voorbeelden

#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;
}

Resultaat

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

De getoonde code en het opgegeven resultaat zijn in een geïsoleerde omgeving geverifieerd met de methode die in het verificatiebewijs voor exact deze versie is vastgelegd.

Bronnen