CKTIS / C
Binarno pretraživanje i lower bound u C-u
Binarno pretraživanje opetovano prepolavlja sortirani raspon pretraživanja. Primjer implementira lower bound: indeks prvog elementa koji nije manji od ključa ili n ako takav element ne postoji. Obrađuje duplikate, prazan unos i siguran izračun sredine.
Verzija: C23; repository compiler flag, production runtime not attested
Sintaksa
size_t lower_bound_int(const int *a, size_t n, int key);Binarno pretraživanje odabire sredinu raspona i odbacuje polovicu koja ne može sadržavati traženi rezultat. Preduvjet sortiranog ulaza ovdje znači da je a[0..n) sortiran neopadajućim redoslijedom prema istom načinu usporedbe koji upotrebljava pretraživanje. Funkcija ne provjerava taj uvjet; nesortirani ulaz može dati netočan rezultat.
Primjer funkcije lower_bound_int implementira lower bound: vraća prvi indeks pos za koji vrijedi a[pos] >= key ili n ako takav indeks ne postoji. Kod duplikata označava prvo pojavljivanje. Sam indeks ne potvrđuje prisutnost ključa: upotrijebite provjeru pos < n && a[pos] == key. Kratko spajanje sprječava da ta provjera čita a[n].
Petlja održava poluotvoreni raspon [lo, hi): elementi prije lo manji su od key, a elementi od hi do n nisu manji od key. Naredba hi = mid zadržava mogući prvi rezultat, dok lo = mid + 1 preskače premalen element. Izraz lo + (hi - lo) / 2 izbjegava prekoračenje pri zbrajanju granica. Kada vrijedi lo == hi, obje granice određuju rezultat.
Za n > 0, a mora sadržavati najmanje n valjanih elemenata koji se ne smiju mijenjati tijekom pretraživanja. Za n == 0, ova implementacija prihvaća NULL i vraća 0 bez čitanja memorije. Za polje je vremenska složenost O(log n) za n >= 2, a dodatni prostor O(1); prethodno sortiranje nije uključeno. C23 je cilj zastavica prevoditelja u repozitoriju, a ne potvrda produkcijskog izvršnog okruženja.
Primjeri
#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
Prikazani kôd i navedeni rezultat provjereni su u izoliranom okruženju metodom zabilježenom u dokazu provjere za ovu točnu verziju.