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.