CKTIS / C
Binarno iskanje in lower bound v C
Binarno iskanje večkrat razpolovi urejeno iskalno območje. Primer implementira lower bound: indeks prvega elementa, ki ni manjši od ključa, ali n, če takega elementa ni. Obravnava dvojnike, prazen vhod in varen izračun sredine.
Različica: C23; repository compiler flag, production runtime not attested
Sintaksa
size_t lower_bound_int(const int *a, size_t n, int key);Binarno iskanje izbere sredino območja in zavrže polovico, ki ne more vsebovati iskanega rezultata. Predpostavka urejenega vhoda tukaj pomeni, da je a[0..n) urejeno naraščajoče ali enako po istem načinu primerjave, kot ga uporablja iskanje. Funkcija tega pogoja ne preveri; neurejen vhod lahko povzroči napačen rezultat.
Zgledna funkcija lower_bound_int implementira lower bound: vrne prvi indeks pos, za katerega velja a[pos] >= key, ali n, če takega indeksa ni. Pri dvojnikih označuje prvo pojavitev. Sam indeks ne potrjuje, da je ključ prisoten: uporabite preizkus pos < n && a[pos] == key. Zaradi kratkostičnega vrednotenja ta preizkus ne bere a[n].
Zanka vzdržuje polodprto območje [lo, hi): elementi pred lo so manjši od key, elementi od hi do n pa niso manjši od key. Ukaz hi = mid ohrani morebitni prvi rezultat, medtem ko lo = mid + 1 preskoči premajhen element. Izraz lo + (hi - lo) / 2 prepreči prekoračitev pri seštevanju mej. Ko velja lo == hi, obe meji določata rezultat.
Za n > 0 mora a zagotavljati vsaj n veljavnih elementov; med iskanjem se ne smejo spreminjati. Za n == 0 ta implementacija sprejme NULL in vrne 0, ne da bi brala pomnilnik. Pri tabeli je časovna zahtevnost O(log n) za n >= 2, dodatni pomnilnik pa O(1); predhodno urejanje ni vključeno. C23 je cilj zastavic prevajalnika v repozitoriju, ne potrditev produkcijskega izvajalnega okolja.
Primeri
#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;
}
Rezultat
key=3 pos=1 found=1 key=4 pos=3 found=0 key=9 pos=4 found=0 empty pos=0
Prikazana koda in navedeni rezultat sta bila preverjena v izoliranem okolju z metodo, zapisano v dokazilu o preverjanju te natančne različice.